Pagini recente » Cod sursa (job #2020599) | Cod sursa (job #3252803) | Cod sursa (job #2451063) | Cod sursa (job #982820) | Cod sursa (job #1116853)
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
char crt;
char a[2000001], b[2000001];
long urmator[2000001], c[1024];
long i,j,M,N,nr;
void initurm()
{
long i, j;
urmator[0] = -1;
for(i = 0, j = -1; i < N; i++, j++, urmator[i] = j)
while(j >= 0 && a[i] != a[j])
j = urmator[j];
}
void kmp()
{
long i,j;
for (i=0, j=0; i<M; i++,j++)
{
while (j>=0 and a[j]!=b[i])
j=urmator[j];
if (j==N-1)
c[nr++]=i-N+1;
}
}
int main ()
{
FILE *f, *g;
f=fopen("strmatch.in", "r");
g=fopen("strmatch.out", "w");
fgets(a, 2000001, f);
fgets(b, 2000001, f);
for (; a[N]!='\n'; ++N);
for (; b[M]!='\n'; ++M);
//URMATOR
urmator[0] = -1;
for(i = 0, j = -1; i < N; ++i, ++j, urmator[i] = j)
while(j > -1 && a[i] != a[j])
j = urmator[j];
//KMP
for (i=0, j=0; i<M; ++i,++j)
{
while (j >- 1 and a[j]!=b[i])
j=urmator[j];
if (j==N-1)
{
c[nr++]=i-N+1;
j=urmator[j];
}
}
fprintf(g, "%d\n", nr);
if (nr>1000) nr=1000;
for (i=0; i<nr; i++) fprintf(g, "%d ", c[i]);
fclose(f); fclose(g);
return 0;
}