Pagini recente » Cod sursa (job #2561575) | Cod sursa (job #2777092) | Cod sursa (job #613928) | Cod sursa (job #487669) | Cod sursa (job #1591147)
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;
int k,n,p[N],a[1005],cnt,i,m;
char T[N],P[N];
void prefix()
{
k=0;
n=strlen(P+1);
for(i=2;i<=n;i++)
{
while(k&&P[i]!=P[k+1])k=p[k];
if(P[i]==P[k+1])
k++;
p[i]=k;
}
}
void kmp()
{
k=0;
n=strlen(T+1);
m=strlen(P+1);
for(i=1;i<=n;i++)
{
while(k&&T[i]!=P[k+1])k=p[k];
if(T[i]==P[k+1])
k++;
if(k==m)
{
cnt++;
if(cnt<=1000)
a[cnt]=i-m;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",P+1,T+1);
prefix();
kmp();
printf("%d\n",cnt);
cnt=cnt<=1000?cnt:1000;
for(i=1;i<=cnt;i++)
printf("%d ",a[i]);
return 0;
}