Pagini recente » Cod sursa (job #2248009) | Cod sursa (job #173237) | Cod sursa (job #1737109) | Cod sursa (job #2186805) | Cod sursa (job #855872)
Cod sursa(job #855872)
#include <cstdio>
#include <cstring>
char s1[2000200];
char s2[2000200];
int n,m;
int p[2000200];
int kmp;
void prefix()
{
int x=0;
for(int i=2;i<=m;i++)
{
while(x>0&&s1[x+1]!=s1[i])
x=p[x];
if(s1[x+1]==s1[i])
x++;
p[i]=x;
}
}
int sol[1010];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
s1[0]=' ';
s2[0]=' ';
scanf("%s%s",s1+1,s2+1);
m=strlen(s1);
m--;
n=strlen(s2);
n--;
prefix();
kmp=0;
for(int i=1;i<=n;i++)
{
while(kmp>0&&s1[kmp+1]!=s2[i])
kmp=p[kmp];
if(s1[kmp+1]==s2[i])
kmp++;
if(kmp==m)
{
kmp=p[m];
sol[0]++;
if(sol[0]<=1000)
sol[sol[0]]=i-1;
}
}
printf("%d\n",sol[0]);
for(int i=1;i<=((sol[0]>1000)?1000:sol[0]);i++)
printf("%d ",sol[i]);
return 0;
}