Cod sursa(job #400796)

Utilizator preda_alexandruPreda Alexandru preda_alexandru Data 21 februarie 2010 22:26:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream.h>
#include<iostream.h>
#include<string.h>

char a[2000001],b[2000001];
int i,k,c,v[1001],pi[2000001],la,lb;

int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

fin.getline(b+1,2000001);
fin.getline(a+1,2000001);

la=strlen(a+1);
lb=strlen(b+1);
c=0;

k=0;
for(i=2;i<=lb;i++)
   {
   while(k>0 && b[k+1]!=b[i])k=pi[k];
   if(b[k+1]==b[i])k++;
   pi[i]=k;
   }

k=0;
for(i=1;i<=la;i++)
   {
   while(k>0 && b[k+1]!=a[i])k=pi[k];
   if(b[k+1]==a[i])k++;
   if(k==lb){
            c++;
            if(c<=1000)v[c]=i-lb;
            }
   }

fout<<c<<'\n';
for(i=1;i<=c && i<=1000;i++)fout<<v[i]<<' ';   

return 0;
}