Pagini recente » Cod sursa (job #1977786) | Cod sursa (job #66408) | Cod sursa (job #408501) | Cod sursa (job #615105) | Cod sursa (job #613541)
Cod sursa(job #613541)
#include<cstdio>
#include<cstring>
using namespace std;
int i,N,M,phi[100001],k,nr=0,a[100001];
char x[100001],s[100001];
void prefix()
{ int i,k;
k=0; phi[1]=0;
for (i=2;i<=N;i++)
{
while (k!=0 && x[i]!=x[k+1]) k=phi[k];
if (x[i]==x[k+1]) k++;
phi[i]=k;
}
}
void kmp ()
{
int i,k=0;
for (i=1;i<=M; i++)
{
while(k!=0 && s[i]!=x[k+1]) k=phi[k];
if (x[k+1]==s[i]) k++;
if (k==N)
{
nr++;
a[nr]=i-k;
k=phi[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(x+1);
gets(s+1);
M=strlen(s+1);N=strlen(x+1);
prefix();
kmp();
printf("%d\n",nr);
for (i=1;i<=nr;i++)
{
printf("%d ",a[i]);
}
return 0;
}