Pagini recente » Cod sursa (job #112676) | Cod sursa (job #2670241) | Cod sursa (job #939199) | Cod sursa (job #2262861) | Cod sursa (job #948182)
Cod sursa(job #948182)
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char p[2000005],t[2000005];
int F[2000005],i,j,m,n,pos[2000005];
void constructie_pi()
{
m=strlen(p);
F[0]=F[1]=0;
for(i=2;i<=m;i++)
{
j=F[i-1];
for(;;)
{
if(p[i-1]==p[j])
{
F[i]=j+1;break;
}
if(j==0)
{
F[i]=0; break;
}
else j=F[j];
}
}
}
void KMP()
{
constructie_pi();
n=strlen(t);
i=0;
j=0;
for(;;)
{
if(j==n)
break;
if(t[j]==p[i])
{
i++;
j++;
if(i==m)
{
pos[0]++;
pos[pos[0]]=j-m;
}
}
else if(i>0) i=F[i];
else j++;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",p);
scanf("%s",t);
KMP();
printf("%d\n",pos[0]);
for(i=1;i<=pos[0];i++)
printf("%d ",pos[i]);
printf("\n");
return 0;
}