Cod sursa(job #1159035)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 29 martie 2014 11:40:16
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
#include<cstring>
int n,m,i,j,nr,v[2100000],p[2100000],q;
char b[2100000],a[2100000];
FILE *f,*g;
int main(){
    f=fopen("strmatch.in","r");
    g=fopen("strmatch.out","w");
    fgets(b+1,2100000,f);
   // fscanf(f,"\n");
    fgets(a+1,2100000,f);
    m=strlen(b+1);
    n=strlen(a+1);
    m--;
    n--;
    p[1]=0;
    for(i=2;i<=m;i++){
        q=p[i];
        while(b[i]!=b[q+1]&&q!=0){
            q=p[q];
        }
        if(b[i]==b[q+1])
            p[i]=q+1;
        else
            p[i]=0;
    }
    q=0;
    for(i=1;i<=n;i++){
        while(a[i]!=b[q+1]&&q!=0){
            q=p[q];
        }
        if(a[i]==b[q+1])
            q++;
        if(q==m){
            q=p[q];
            v[++nr]=i-m;
        }
    }
    fprintf(g,"%d\n",nr);
    if(n>1000)
        n=1000;
    for(i=1;i<=nr;i++){
        fprintf(g,"%d ",v[i]);
    }


    fclose(f);
    fclose(g);
    return 0;
}