Cod sursa(job #724238)

Utilizator ndranrawPetrisor Andrei ndranraw Data 26 martie 2012 12:47:27
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
using namespace std;
ifstream fi( "strmatch.in" );
ofstream fo( "strmatch.out" );
int M,N,pi[2000000],pos[1024];
char A[2000000],B[2000000],c;
int main()
{int i, q = 0, n = 0;
while ( (c=fi.get()) && (c!='\n') )
	A[++M]=c;
while ( (c=fi.get()) && (c!='\n') && (c!=EOF) )
	B[++N]=c;
for (i = 2, pi[1] = 0; i <= M; ++i)
{
     while (q && A[q+1] != A[i])
         q = pi[q];
         if (A[q+1] == A[i])
             ++q;
		 pi[i] = q;
}for (i = 1; i <= N; ++i)
{       
while (q && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
++q;
if (q == M)
{
q = pi[M];
++n;
if (n <= 1000)
pos[n] = i-M;
}}fo<<n<<'\n';
if( n> 1000 )			 
	n=1000;
for ( i=1; i<=n; i++ )
	fo<<pos[i]<<' ';
fi.close();
fo.close();
}