Cod sursa(job #293374)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 1 aprilie 2009 18:13:51
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
#include<string.h>
using namespace std;
char a[2000010],b[2000010];
int n,m,i,q,pi[2000010],sol,v[2000010],k;

int main()
{

ifstream f("strmatch.in");
ofstream g("strmatch.out");

f.get(a+1,2000005); f.get();
f.get(b+1,2000005);
a[0]=b[0]='a';

n=strlen(a)-1;

k=0; pi[1]=0;

 for(i=2;i<=n;i++)

  { while ( (k>0) && (a[k+1]!=a[i]) )

    k=pi[k];

     if(a[k+1]==a[i])
       k++;

     pi[i]=k;
  }

m=strlen(b)-1;

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)  v[++sol]=i-n;
  }
g<<sol<<'\n';
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++) g<<v[i]<<" ";

f.close();
g.close();
return 0;
}