Pagini recente » Cod sursa (job #2633454) | Cod sursa (job #137520) | Cod sursa (job #837952) | Cod sursa (job #890297) | Cod sursa (job #2730708)
#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 && A[k + 1] != B[i])
k = p[k];
if(A[k + 1] == B[i])
++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;
prefix();
KMP();
g << nr << '\n';
if(nr >= 1000)nr = 1000;
for(int i = 1; i <= nr; ++i)
g << sol[i] << ' ';
return 0;
}