Pagini recente » Cod sursa (job #41383) | Cod sursa (job #2219724) | Cod sursa (job #389495) | Cod sursa (job #2700786) | Cod sursa (job #1116802)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
char crt;
char a[2000001], b[2000001];
long urmator[2000001], c[2000001];
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");
fscanf(f, "%c", &crt);
while (crt!='\n')
{
a[N++]=crt;
fscanf(f, "%c", &crt);
}
fscanf(f, "%c", &crt);
while (crt!='\n')
{
b[M++]=crt;
fscanf(f, "%c", &crt);
}
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];
for(i = 0, j = 0; i < M; i++, j++)
{
while(j >= 0 && b[i] != a[j])
j = urmator[j];
if (j==N-1)
c[nr++]=i-N+1;
}
fprintf(g, "%d\n", nr);
for (i=0; i<nr && i<1000; i++) fprintf(g, "%d ", c[i]);
fclose(f); fclose(g);
return 0;
}