Pagini recente » Cod sursa (job #309662) | Cod sursa (job #975103) | Cod sursa (job #242459) | Cod sursa (job #560351) | Cod sursa (job #2863059)
//#include <iostream>
#include <fstream>
using namespace std;
const int NMAX = 2000002;
char A[NMAX], B[NMAX];
int m, n,
p[NMAX],
sol[1001], nr;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void prefix()
{
int k = 0;
p[1] = 0;
for(int i = 2; i <= m; i++)
{
while(k > 0 && A[i] != A[k + 1])
k = p[k];
if(A[i] == A[k + 1])
k++;
p[i] = k;
}
}
void KMP()
{
int k = 0;
for(int i = 1; i <= n; i++)
{
while(k > 0 && B[i] != A[k + 1])
k = p[k];
if(B[i] == A[k + 1])
k++;
if(k == m)
{
nr++;
if(nr <= 1000)
sol[nr] = i - m;
k = p[k];
}
}
}
int main()
{
f.getline(A + 1, NMAX);
m = f.gcount() - 1;
f.getline(B + 1, NMAX);
n = f.gcount() - 1;
//cout << m << ' ' << n << '\n';
prefix();
KMP();
g << nr << '\n';
if(nr >= 1000) nr = 1000;
for(int i = 1; i <= nr; i++)
g << sol[i] << ' ';
return 0;
}