Pagini recente » Cod sursa (job #1145317) | Cod sursa (job #76500) | Cod sursa (job #2866101) | Cod sursa (job #2056639) | Cod sursa (job #2038408)
#include <iostream>
#include <string.h>
#include <fstream>
#define NM 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char c,H[NM],N[NM];
int n,h,f,S[NM],k,cnt,sol[NM];
int main()
{
in>>N+1;
n=strlen(N+1);
S[0]=-1;
S[1]=0;
for(int i=2;i<=n;++i)
{
k=i-1;
c=N[i];
while(S[k]!=-1 && N[S[k]+1]!=c)k=S[k];
S[i]=S[k]+1;
}
in>>H+1;
h=strlen(H+1);
///bine(teoretic)
for(int i=1;i<=h;++i)
{
while(f!=-1)
{
if(N[f+1]==H[i])break;
else f=S[f];
}
if(f==-1)f=0;
else
{
f++;
if(f==n)
{
sol[++cnt]=i-n;
f=S[f];
}
}
}
out<<cnt<<'\n';
for(int i=1;i<=min(cnt,1000);++i)out<<sol[i]<<" ";
return 0;
}