Pagini recente » Cod sursa (job #2663233) | Cod sursa (job #1546873) | Cod sursa (job #2766253) | Cod sursa (job #2406037) | Cod sursa (job #1207492)
#include<cstdio>
#include<fstream>
#include<cstring>
using namespace std;
#define NMAX 2000004
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,r,q,st[1005],p[NMAX+1];
char A[NMAX+1],B[NMAX+1];
void prefix()
{
int i;
q=0;
for (i=2;i<=n;++i)
{
while (A[i]!=A[q+1] && q>0)
q=p[q];
if (A[i]==A[q+1])
++q;
p[i]=q;
}
}
int main()
{
int i;
f.getline(A+1,NMAX);
f.getline(B+1,NMAX);
n=strlen(A+1), m=strlen(B+1);
prefix();
q=0;
for (i=1;i<=m;++i)
{
while (B[i]!=A[q+1] && q>0)
q=p[q];
if (B[i]==A[q+1])
++q;
if (q==n)
{
++r;
if (r<1001) st[r]=i-n;
q=p[q];
}
}
g<<r<<"\n";
r=min(r,1000);
for (i=1;i<=r;++i)
g<<st[i]<<" ";
g<<"\n";
return 0;
}