Pagini recente » Cod sursa (job #861337) | Cod sursa (job #1083010) | Cod sursa (job #2914003) | Cod sursa (job #2181653) | Cod sursa (job #1291998)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NM 2000000 + 10
#define F 1000 + 10
int i,n,m,SOL;
int p[NM], S[F];
char a[NM], b[NM];
using namespace std;
void prefix()
{
int q=0; p[1]=0;
for (int i=2;i<=n;++i)
{
while (q && a[q+1]!=a[i])
q=p[q];
if (a[q+1]==a[i])
++q;
p[i]=q;
}
}
void kmp()
{
int q=0;
for (int i=1;i<=m;++i)
{
while (q && a[q+1]!=b[i])
q=p[q];
if (a[q+1]==b[i])
++q;
if (q==n)
{
q=p[n];
SOL++;
if (SOL<=1000) S[SOL]=i-n;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1); n=strlen(a+1);
gets(b+1); m=strlen(b+1);
prefix();
kmp();
printf("%d\n", SOL);
for (i=1;i<=min(SOL,F-10);++i)
printf("%d ", S[i]);
return 0;
}