Pagini recente » Cod sursa (job #1550857) | Cod sursa (job #289917) | Cod sursa (job #328914) | Cod sursa (job #915545) | Cod sursa (job #359759)
Cod sursa(job #359759)
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,q,k,i,nr,urm[2000000],v[100];
char s[2000000],p[2000000];
int main ()
{
f.getline(p,1000);
f.getline(s,1000);
m=strlen(p);
for(i=m;i>=0;i--)
p[i+1]=p[i];
p[0]=' ';
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=n;i>=0;i--)
s[i+1]=s[i];
s[0]=' ';
q=0;
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;
}