Pagini recente » Cod sursa (job #2945179) | Cod sursa (job #2186679) | Cod sursa (job #993370) | Cod sursa (job #1521129) | Cod sursa (job #298967)
Cod sursa(job #298967)
#include <stdio.h>
#include <string.h>
#define Nmax 2000001
char s1[Nmax],s2[Nmax],x[Nmax];
int pi[Nmax],Y[Nmax];
void cit()
{
scanf("%s\n",&x);
strcpy(s2+1,x);
scanf("%s",&x);
strcpy(s1+1,x);
}
void prefix()
{
int n=strlen(s2+1),k,i;
k=0;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&s2[k+1]!=s2[i])
k=pi[i];
if(s2[k+1]==s2[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int m=strlen(s1+1),n=strlen(s2+1),q,i;
prefix();
q=0;
for(i=1;i<=m;i++)
{
while(q>0&&s2[q+1]!=s1[i])
q=pi[q];
if(s2[q+1]==s1[i])
q++;
if(q==n)
Y[++Y[0]]=i-n+1;
//printf("%d ",i-n+1);
}
}
void scr()
{
int i;
printf("%d\n",Y[0]);
for(i=1;i<=Y[0];i++)
printf("%d ",Y[i]);
}
int main()
{
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
cit();
kmp();
scr();
return 0;
}