Pagini recente » Cod sursa (job #637301) | Cod sursa (job #10971) | Cod sursa (job #301343) | Cod sursa (job #809847) | Cod sursa (job #335303)
Cod sursa(job #335303)
#include <stdio.h>
#include <string.h>
#define DIM 2000005
#define MAX 1005
char a[DIM],b[DIM];
int pi[DIM],poz[MAX];
int n,m,nrt;
void read ()
{
gets (a+1);
n=strlen (a+1);
gets (b+1);
m=strlen (b+1);
}
void kmp (char a[DIM])
{
int i,k;
for (k=0, i=2; i<=n; ++i)
{
for ( ; a[k+1]!=a[i] && k>0; )
k=pi[k];
if (a[k+1]==a[i])
++k;
pi[i]=k;
}
}
void solve ()
{
int i,k;
for (k=0, i=1; i<=m; ++i)
{
for ( ; a[k+1]!=b[i] && k>0; )
k=pi[k];
if (a[k+1]==b[i])
++k;
if (k==n)
{
++nrt;
if (nrt<=1000)
poz[nrt]=i-n;
k=pi[k];
}
}
}
int min (int a,int b)
{
if (a<b)
return a;
return b;
}
void print ()
{
int i,t;
printf ("%d\n",nrt);
for (i=1, t=min (nrt,1000); i<=t; ++i)
printf ("%d ",poz[i]);
}
int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
read ();
kmp (a);
solve ();
print ();
return 0;
}