Pagini recente » Cod sursa (job #2934722) | Cod sursa (job #2920039) | Cod sursa (job #190238) | Cod sursa (job #1351895) | Cod sursa (job #1389906)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define minim(a,b) a<b?a:b
using namespace std;
int n, m;
int urm[NMAX],pos[NMAX], nr;
char T[NMAX], P[NMAX];
void citire()
{
gets(P);
gets(T);
m=strlen(P);
n=strlen(T);
}
void make_prefix(char *P)
{
int k=-1, x;
urm[0]=0;
for(x=1;x<m;++x)
{
while(k>=0&&P[k+1]!=P[x])
k=urm[k];
if(P[k+1]==P[x])
++k;
urm[x]=k;
}
}
void KMP()
{
make_prefix(P);
int i, x=-1;
for(i=0;i<n;++i)
{
while(x>=0&&P[x+1]!=T[i])
x=urm[x];
if(P[x+1]==T[i])
++x;
if(x==m-1)
{
++nr;
if(nr<=1000)
pos[nr]=i-m+1;
x=urm[x];
}
}
}
void afisare()
{
int i;
int POZ=minim(nr, 1000);
printf("%d\n", nr);
for(i=1;i<=POZ;++i)
printf("%d ", pos[i]);
printf("\n");
}
void rezolva_problema()
{
citire();
KMP();
afisare();
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
rezolva_problema();
return 0;
}