Pagini recente » Cod sursa (job #2652728) | Cod sursa (job #2203038) | Cod sursa (job #870609) | Cod sursa (job #971795) | Cod sursa (job #2195241)
#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(a[j]==b[j])
++j;
}
if(j==sa)
{
++cate;
f[cate]=i-sa+1;
j=sp[j-1];
}
}
out<<cate<<"\n";
if(cate>1000)
cate=1000;
for(i=1; i<=cate; ++i)
out<<f[i]<<" ";
return 0;
}