Pagini recente » Cod sursa (job #882201) | Cod sursa (job #2083078) | Cod sursa (job #2305050) | Cod sursa (job #1007497) | Cod sursa (job #157559)
Cod sursa(job #157559)
#include<cstdio>
#include<cstring>
using namespace std;
char a[2000001],b[2000001];
int n,m,i,j,k,pi[20000001],s[1001];
inline void kmp()
{
n=strlen(a);
k=-1;
pi[0]=-1;
for(i=1;i<n;i++){
while(k>=0 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;}
m=strlen(b);
k=-1;
for(i=0;i<m;i++){
while(k>=0 && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i]) k++;
if(k==n-1) {
s[0]++;
if(s[0]<=1000) s[s[0]]=i-n+1;}}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",a,b);
kmp();
printf("%d\n",s[0]);
for(i=1;i<=1000&&i<=s[0];i++)
printf("%d ",s[i]);
fclose(stdout);
return 0;
}