Pagini recente » Cod sursa (job #572084) | Cod sursa (job #490759) | Monitorul de evaluare | Cod sursa (job #1205093) | Cod sursa (job #395484)
Cod sursa(job #395484)
#include <algorithm>
using namespace std;
#define DIM 2000005
#define MAX 1005
char s1[DIM],s2[DIM];
int pi[DIM],sol[MAX];
int n,m,nrt;
void read ()
{
fgets (s1+1,DIM,stdin);
n=strlen (s1+1)-1;
fgets (s2+1,DIM,stdin);
m=strlen (s2+1)-1;
}
void prefix ()
{
int i,k;
for (k=0, i=2; i<=n; ++i)
{
for ( ; k>0 && s1[k+1]!=s1[i]; k=pi[k]);
if (s1[k+1]==s1[i])
++k;
pi[i]=k;
}
}
void kmp ()
{
int i,k;
prefix ();
for (k=0, i=1; i<=m; ++i)
{
for ( ; k>0 && s1[k+1]!=s2[i]; k=pi[k]);
if (s1[k+1]==s2[i])
++k;
if (k==n)
{
if (++nrt<MAX)
sol[nrt]=i-n;
k=pi[k];
}
}
}
void print ()
{
int i;
printf ("%d\n",nrt);
for (i=1; i<=nrt; ++i)
{
if (i>1000)
return ;
printf ("%d ",sol[i]);
}
}
int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
read ();
kmp ();
print ();
return 0;
}