Pagini recente » Cod sursa (job #658408) | Cod sursa (job #2120395) | Cod sursa (job #3231064) | Cod sursa (job #668511) | Cod sursa (job #1116850)
#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] >= 'A' && a[N] <= 'Z') || (a[N] >= 'a' && a[N] <= 'z')
|| (a[N] >= '0' && a[N] <= '9'); ++N);
for (; (b[M] >= 'A' && b[M] <= 'Z') || (b[M] >= 'a' && b[M] <= 'z')
|| (b[M] >= '0' && b[M] <= '9'); ++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;
}