Pagini recente » Cod sursa (job #2170051) | Rating lolly lolly689 (lolly690) | Cod sursa (job #1903771) | Cod sursa (job #2982235) | Cod sursa (job #359777)
Cod sursa(job #359777)
#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;
}