Pagini recente » Cod sursa (job #1380884) | Cod sursa (job #781558) | Cod sursa (job #1204616) | Cod sursa (job #2522924) | Cod sursa (job #2730495)
//#include <iostream>
#include <fstream>
using namespace std;
const int NMAX = 2000001;
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 = -1;
p[0] = 0;
for(int i = 1; i < n; 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 = -1;
for(int i = 0; i < n; i++)
{
while(k > 0 && A[k + 1] != B[i])
k = p[k];
if(A[k + 1] == B[i])
k++;
if(k == m - 1)
{
nr++;
if(nr <= 1000)
sol[nr] = i - m + 1;
k = p[k];
}
}
}
int main()
{
f.getline(A, NMAX);
m = f.gcount() - 1;
f.getline(B, 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;
}