Pagini recente » Cod sursa (job #1091123) | Cod sursa (job #596789) | Cod sursa (job #2082940) | Cod sursa (job #3204180) | Cod sursa (job #1389869)
#include <cstdio>
#include <fstream>
#include <cstring>
#define NMAX 2000005
#define minim(a,b) a<b?a:b
using namespace std;
ifstream fin("strmatch.in");
int n, m;
int urm[NMAX],pos[NMAX], nr;
char T[NMAX], P[NMAX];
void citire()
{
char x;
fin.get(P, NMAX);
fin>>x;
fin.get(T,NMAX);
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]+1);
printf("\n");
}
void rezolva_problema()
{
citire();
KMP();
afisare();
}
int main()
{
freopen("strmatch.out", "w", stdout);
rezolva_problema();
return 0;
}