Cod sursa(job #156998)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 12 martie 2008 20:25:32
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstring>
#include <cstdio>
const int nmax=2000000;
char a[nmax],b[nmax];
int pi[nmax],poz[1000],n,m;
void prefix(){
     int i,k;
     pi[0]=-1;pi[1]=0;
     for (i=2,k=0;i<=n;i++) {
         while (k>0 && a[i-1]!=a[k]) k=pi[k];
         if (a[i-1]==a[k]) k++;
         pi[i]=k;}
}
void search(){
     int i,k;
     for (i=0,k=0;i+k<m;){
         if (a[k]==b[i+k]){k++;
                           if (k==n) {poz[0]++;
                                      if (poz[0]<=1000) poz[poz[0]]=i;
                                      i=i+n-pi[n];
                                      k=pi[n];}
                           }
                     else {i=i+k-pi[k];
                           if (k>0) k=pi[k];}
                           }
}
int main(){
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",a,b);
    n=strlen(a);
    m=strlen(b);
    prefix();
    search();
    printf("%d\n",poz[0]);
    if (poz[0]>1000) poz[0]=1000;
    for (i=1;i<=poz[0];i++) printf("%d ",poz[i]);
    fclose(stdout);
}