Pagini recente » Cod sursa (job #1109403) | Cod sursa (job #862685) | Cod sursa (job #874096) | Cod sursa (job #2307090) | Cod sursa (job #1528608)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s1[2000003],s2[2000003];
int x[2000001];
int s[1001];
int main()
{
int k1,k2,c, kmp, sol=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",s1,s2);
k1=strlen(s1);
k2=strlen(s2);
if(k1>k2)
printf("0");
else
{
for(int i=k1; i>0; i--)
s1[i]=s1[i-1];
s1[k1+1]='\0';
for(int i=k2; i>0; i--)
s2[i]=s2[i-1];
s2[k2+1]='\0';
for(int i=2; i<=k1; i++)
{
c=i;
while(s1[i]!=s1[x[c-1]+1] && c>1)
c=x[c-1]+1;
x[i]=c;
if(c==1 && s1[1]!=s1[i])
x[i]=0;
}
kmp=1;
for(int i=1; i<=k2; i++)
{
while(s2[i]!=s1[kmp+1] && kmp>1)
kmp=x[kmp-1]+1;
x[i]=kmp;
if(kmp==1 && s2[i]!=s1[1])
x[i]=0;
}
for(int i=1; i<=k2 && sol<1000; i++)
{
if(x[i]==k1)
{
s[sol]=i-1;
sol++;
}
}
printf("%d\n",sol);
for(int i=0;i<sol; i++)
printf("%d ",s[i]);
}
return 0;
}