Cod sursa(job #693664)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 27 februarie 2012 15:14:03
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream>
int urm[2000002],n,m,i,x=-1,c[2000002],q;
char a[2000002],b[2000002];
void urmatorul(char *b)
{
	int k=-1 ,x;
	urm[0]=0;
	for(x=1;x<m;x++)
	{
		while(k>0 && b[k+1]!=b[x])k=urm[k];
		if(b[k+1]==b[x])k++;
		urm[x]=k;
	}
}

using namespace std;
int main()
{
	ifstream f("strmatch.in");ofstream g("strmatch.out");
	f.getline(b,1000); m=strlen(b);
	f.getline(a,1000); n=strlen(a);
	urmatorul(b);
	for(i=0;i<n;i++)
	{
		while(x>0 && b[x+1]!=a[i]) x=urm[x];
		if(b[x+1]==a[i])x++;
		if(x==m-1)
		{
			c[++q]=i-m+1;
			x=urm[x];
		}
	}
	g<<q<<'\n';
	for(i=1;i<=q;i++) g<<c[i]<<' ';
	f.close();g.close();
return 0;}