Pagini recente » Cod sursa (job #865691) | Cod sursa (job #924867) | Cod sursa (job #831734) | Cod sursa (job #1218706) | Cod sursa (job #1389571)
#include <cstdio>
#include <cstring>
#define DMAX 2000010
using namespace std;
char a[DMAX], b[DMAX];
int n, m;
int lg[DMAX];
int lgsol, sol[DMAX];
void citire();
void prefix();
void KMP();
void afisare();
int main()
{
citire();
prefix();
KMP();
afisare();
return 0;
}
void citire()
{
FILE*fin=fopen ("strmatch.in", "r");
fscanf(fin, "%s", a);
fscanf(fin, "%s", b);
n=strlen (a); m=strlen (b);
fclose(fin);
return;
}
void prefix()
{
int i, k;
lg[1]=0;
for (i=2; i<=n; ++i)
{
k=lg[i-1];
while (k>0 && a[k+1]!=a[i])
k=lg[k];
if (a[k+1]==a[i])
++k;
lg[i]=k;
}
return;
}
void KMP()
{
int i, k=0;
for (i=1; i<=m; ++i)
{
while (k>0 && a[k+1]!=b[i])
k=lg[k];
if (a[k+1]==b[i])
++k;
if (k==n)
{
sol[++lgsol]=i-n;
k=lg[k];
}
}
return;
}
void afisare()
{
int i;
FILE*fout=fopen ("strmatch.out", "w");
fprintf(fout, "%d\n", lgsol);
for (i=1; i<=lgsol; ++i)
fprintf(fout, "%d ", sol[i]);
fprintf(fout, "\n");
fclose(fout);
return;
}