Cod sursa(job #249410)

Utilizator ConsstantinTabacu Raul Consstantin Data 28 ianuarie 2009 13:27:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
#include<string.h>
long long int n,m,nr,sol[1001],i,q,j,pi[200011];
char a[200011],b[200011];
int main(){
FILE *f=fopen("strmatch.in","r");
fscanf(f,"%s %s",a+1,b+1);
fclose(f);
n=strlen(a+1);
m=strlen(b+1);
q=0;
for(i=2;i<=n;++i)
        {while((q>0)&&(a[q+1]!=a[i]))
                q=pi[q];
        if(a[q+1]==a[i])q++;
        pi[i]=q;

        }
q=0;
for(i=1;i<=m;++i)
        {while((q>0)&&(a[q+1]!=b[i]))
                q=pi[q];
        if(a[q+1]==b[i])
                q++;
        if(q==n)
                {nr++;
                sol[nr]=i-n;}
       }
FILE *g=fopen("strmatch.out","w");
fprintf(g,"%lld\n",nr);

for(i=1;i<=nr&&i<=1000;i++)
        fprintf(g,"%lld ",sol[i]);
fclose(g);
return 0;}