Pagini recente » Cod sursa (job #1157545) | Cod sursa (job #203041) | Cod sursa (job #812920) | Cod sursa (job #129459) | Cod sursa (job #1290630)
#include <bits/stdc++.h>
using namespace std;
char A[2000005],B[2000005];
int i,k,na,nb,pr[2000005],s[1010],sol;
inline void prefix()
{
k=0;
na=strlen(A+1);
for(i=2;i<=na;i++)
{
while(k&&A[i]!=A[k+1])k=pr[k];
if(A[i]==A[k+1])k++;
pr[i]=k;
}
}
inline void kmp()
{
k=0;
nb=strlen(B+1);
for(i=2;i<=nb;i++)
{
while(k&&B[i]!=A[k+1])k=pr[k];
if(B[i]==A[k+1])k++;
if(k==na)
{
sol++;
if(sol<=1000)
s[sol]=i-na;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A+1,B+1);
prefix();
kmp();
printf("%d\n",sol);
sol=min(sol,1000);
for(i=1;i<=sol;i++)
printf("%d ",s[i]);
return 0;
}