Cod sursa(job #359780)

Utilizator piuaruanapiuaru ana maria piuaruana Data 28 octombrie 2009 12:03:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream.h>
#include<string.h>
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long nr,n,m,k,q,i;
int urm[2000001],v[2000001];
char t[2000001],p[2000001],aux[2000001];
int main()
{f.get(t,2000000);
f.get();
f.get(p,2000000);
m=strlen(p);
n=strlen(t);
strcpy(aux," ");
strcat(aux,t);
strcpy(t,aux);
strcpy(aux," ");
strcat(aux,p);
strcpy(p,aux);
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;
}
q=0;
nr=0;
for(i=1;i<=n;i++)
{while(q>0&&p[q+1]!=t[i])
	q=urm[q];
if(p[q+1]==t[i])
	q++;
if(q==m)
	{nr++;
v[nr]=i-m;
q=urm[q];}
}
g<<nr<<'\n';
for(i=1;i<=nr;i++)
	g<<v[i]<<' ';
f.close();
g.close();
return 0;
}