Pagini recente » Cod sursa (job #1989247) | Cod sursa (job #2350862) | Cod sursa (job #1410782) | Cod sursa (job #878600) | Cod sursa (job #1117117)
#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;
char crt;
char a[2000001], b[2000001];
int urmator[2000001], c[2000001];
int 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);
}
*/
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a;
f.get();
f>>b;
f.close();
N=strlen(a)-1;
M=strlen(b)-1;
urmator[0] = -1;
for(i = 1, j = 0; i < N; ++i, ++j, urmator[i] = j)
while(j > -1 && a[i] != a[j])
j = urmator[j];
for(i = 0, j = 0; i < M; ++i, ++j)
{
while(j > -1 && b[i] != a[j])
j = urmator[j];
if (j==N-1)
{
if (nr<1000) c[nr]=i-N+1;
++nr;
}
}
g<<nr<<"\n";
if (nr>1000) nr=1000;
for (i=0; i<nr; ++i) g<<c[i]<<" ";
g<<"\n";
/* 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;
}