Pagini recente » Cod sursa (job #2357796) | Cod sursa (job #3245725) | Cod sursa (job #310422) | Cod sursa (job #2385771) | Cod sursa (job #1116784)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
char crt;
char a[2000001], b[2000001];
long urmator[2000001];
vector <long> c;
long i,j,M,N,nr;
void brute()
{
int ok;
long i,j;
for(i=0; i<=M; i++)
{
for(j=0, ok=1; j<N and ok; j++)
if (a[j]!=b[i+j]) ok=0;
if (ok) c.push_back(i);
}
}
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.push_back(i-N+1);
nr++;
}
}
}
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);
}
//cout<<N<<" "<<M;
initurm();
kmp();
//brute();
fprintf(g, "%d\n", nr);
for (i=0; i<nr && i<1000; i++) fprintf(g, "%d ", c[i]);
fclose(f); fclose(g);
return 0;
}