Pagini recente » Cod sursa (job #1155461) | Cod sursa (job #889042) | Cod sursa (job #2571391) | Cod sursa (job #930745) | Cod sursa (job #1145064)
#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;
}