Pagini recente » Cod sursa (job #2569981) | Cod sursa (job #922067) | Cod sursa (job #586101) | Cod sursa (job #1656562) | Cod sursa (job #2195226)
#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])
{
++j;
sp[i]=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];
}
if(cate==1000)
break;
}
out<<cate<<"\n";
for(i=1; i<=k; ++i)
out<<f[i]<<" ";
return 0;
}