Pagini recente » Cod sursa (job #1050659) | Cod sursa (job #721271) | Cod sursa (job #2720778) | Statistici Raceanu Dragos-Ion (Raceanud) | Cod sursa (job #549238)
Cod sursa(job #549238)
#include <cstdio>
#include <string.h>
#define MaxN 2000010
char N[MaxN],M[MaxN];
int n,m,pi[MaxN],Nr,s[1001];
void cit()
{
scanf("%s",&N);
n=strlen(N);
scanf("%s",&M);
m=strlen(M);
}
void translatie()
{
int i;
for(i=n-1;i>=0;i--)
N[i+1]=N[i];
for(i=m-1;i>=0;i--)
M[i+1]=M[i];
}
void prefix()
{
int i,k;
k=0;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(k>0 && N[k+1]!=N[i])
k=pi[k];
if(N[k+1]==N[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int i,q=0;
for(i=1;i<=m;i++)
{
while(q>0 && N[q+1]!=M[i])
q=pi[q];
if(N[q+1]==M[i])
q++;
if(q==n)
{
Nr++;
if(Nr<=1000)
s[Nr]=i-n+1;
}
}
}
int minim(int a,int b)
{
return (a<b)? a:b;
}
void afis()
{
printf("%d\n",Nr);
int min=minim(Nr,1000);
for(int i=1;i<=min;i++)
{
printf("%d ",s[i]-1);
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cit();
translatie();
prefix();
kmp();
afis();
fclose(stdin);
fclose(stdout);
return 0;
}