Pagini recente » Cod sursa (job #1388157) | Cod sursa (job #1949698) | Cod sursa (job #570179) | Cod sursa (job #1087025) | Cod sursa (job #2039939)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000001],b[2000001],c;
int n,h,S[2000001],s[2000001];
int k,f,ap;
int main()
{
in>>a+1;
n=strlen(a+1);
in>>b+1;
h=strlen(b+1);
S[0]=-1;
S[1]=0;
for(int i=2;i<=n;i++)
{
k=i-1;
c=a[i];
while(S[k]!=-1 && a[S[k]+1]!=c)
k=S[k];
S[i]=S[k]+1;
}
for(int i=1;i<=h;i++)
{
while(f!=-1)
if(a[f+1]==b[i])
break;
else
f=S[f];
if(f==-1)
f=0;
else
{
f++;
if(f==n)
{
ap++;
s[ap]=i-n;
f=S[f];
}
}
}
out<<ap<<"\n";
for(int i=1;i<=min(ap,1000);i++)
out<<s[i]<<" ";
return 0;
}