Cod sursa(job #195292)

Utilizator rethosPaicu Alexandru rethos Data 17 iunie 2008 14:46:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream.h>
#define NM 2000001
#define MM 2000001
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
int pi[MM];
char a[NM],b[MM];
int poz[1001];
void comput()
{pi[0]=0;
 int i,x=0;
 for (i=1;i<n;i++)
        {while (x>0 && a[x]!=a[i]) x=pi[x-1];
         if (a[x]==a[i]) x++;
         pi[i]=x;
        }
}
void kmp()
{int i,x=0;
 int nr=0;
 for (i=0;i<m;i++)
        {while (x>0 && a[x]!=b[i]) x=pi[x-1];
         if (a[x]==b[i]) x++;
         if (x==n) {nr++;
                    if (nr<=1000) poz[nr]=i-n+1;
                    x=pi[x-1];
                   }
        }
 fout<<nr<<'\n';
 for (i=1;i<=nr&&i<=1000;++i)
        fout<<poz[i]<<' ';
}
int main()
{fin>>a;
 fin>>b;
 n=strlen(a);
 m=strlen(b);
 comput();
 kmp();
 return 0;
}