Pagini recente » Cod sursa (job #1204551) | Cod sursa (job #1312809) | Cod sursa (job #2519074) | Cod sursa (job #2316226) | Cod sursa (job #2195225)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000005], b[2000005];
int i, n, sa, sb, sp[2000005], j, k, f[2000005], cate;
int main()
{
in>>a;
in>>b;
sa=strlen(a);
sb=strlen(b);
j=0;
sp[j]=0;
for(i=1; i<sa; ++i)
{
if(a[i]==a[j])
{
sp[i]=j+1;
++j;
}
else
{
while(j>0 && a[j]!=a[i])
{
j=sp[j-1];
}
if(a[i]==a[j])
{
sp[i]=j+1;
++j;
}
else
sp[i]=0;
}
}
j=0;
for(i=0; i<sb; ++i)
{
if(a[j]==b[i])
++j;
else
{
while(j!=0 && a[j]!=b[i])
j=sp[j-1];
}
if(j==sa)
{
++cate;
f[++k]=i-sa+1;
j=sp[j-1];
}
}
out<<cate<<"\n";
for(i=1; i<=k; ++i)
out<<f[i]<<" ";
return 0;
}