Cod sursa(job #576903)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 9 aprilie 2011 16:57:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
using namespace std;
#include<fstream>
char s[2000100],ss[2000100];
int pi[2000100],sol[1010];
int main()
{int m,i,q,nr=0;
ifstream in("strmatch.in");
in.getline(s,2000030);
in.getline(ss,2000030);
in.close();
q=0;
m=strlen(s);
for(i=1;s[i];i++)
	{while(q&&s[q]!=s[i])
		q=pi[q-1];
	if(s[q]==s[i])
	q++;
	pi[i]=q;
	}
q=0;
for(i=0;ss[i];i++)
	{while(q&&s[q]!=ss[i])
		q=pi[q-1];
	if(s[q]==ss[i])
	q++;
	if(q==m)
		{q=pi[m-1];
		nr++;
		if(nr<=1000)
		sol[nr]=i-m+1;
		}
	}
ofstream out("strmatch.out");
out<<nr<<'\n';
for(i=1;i<=min(nr,1000);i++)
	out<<sol[i]<<" ";
out<<'\n';
out.close();
return 0;
}