Cod sursa(job #359777)

Utilizator avram_florinavram florin constantin avram_florin Data 28 octombrie 2009 12:01:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,q,k,i,nr,urm[2000001],v[1000001];
char s[2000001],p[2000001],aux[2000001];
int main ()
{
	f.getline(aux,2000000);
p[0]=' ';
strcat(p,aux);
f.getline(aux,2000000);
s[0]=' ';
strcat(s,aux);
m=strlen(p);
urm[1]=0;
k=0;
for(q=2;q<=m;q++)
	{while(k>0&&p[k+1]!=p[q])
		 k=urm[k];
	if(p[k+1]==p[q])
		k++;
	urm[q]=k;
	}
n=strlen(s);
for(i=1;i<=n;i++)
   {while(q>0&&p[q+1]!=s[i])
	     q=urm[q];
    if(p[q+1]==s[i])
		q++;
	if(q==m)
	   {nr++;
	    v[nr]=i-m;
	   }
   }
g<<nr<<'\n';
for(i=1;i<=nr;i++)
	g<<v[i]<<' ';
g<<'\n';
f.close();
g.close();
return 0;
}