Pagini recente » Cod sursa (job #1407868) | Cod sursa (job #162293) | Cod sursa (job #2880625) | Cod sursa (job #2754644) | Cod sursa (job #361597)
Cod sursa(job #361597)
#include <stdio.h>
#include <algorithm>
#define MAXN 2000010
char a[MAXN], b[MAXN];
int pi[MAXN], poz[1002];
int i,n,m,sol,q;
void prefix()
{
int i,q=0;
pi[1]=0;
for (i=2; i<=n; i++)
{
while (q && a[q+1]!=a[i]) q=pi[q];
if (a[q+1]==a[i]) q++;
pi[i]=q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,MAXN,stdin);
fgets(b,MAXN,stdin);
n=strlen(a); m=strlen(b);
for(i=n; i>=1; i--) a[i]=a[i-1];
for(i=m; i>=1; i--) b[i]=b[i-1];
a[0]=b[0]=' '; n--;
prefix();
q=sol=0;
for (i=1; i<=m; i++)
{
while (q && a[q+1]!=b[i]) q=pi[q];
if (a[q+1]==b[i]) q++;
if (q==n)
{
sol++;
if (sol<1001) poz[sol]=i-n;
q=pi[q];
}
}
printf("%d\n",sol);
if (sol>1000) sol=1000;
for (i=1; i<=sol; i++)
printf("%d ",poz[i]);
printf("\n");
return 0;
}