Pagini recente » Cod sursa (job #1394466) | Cod sursa (job #2140294) | Cod sursa (job #1515628) | Cod sursa (job #2433262) | Cod sursa (job #1868917)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int DIM = 2000001;
char A[DIM], B[DIM];
int N, M, match[DIM], nr = 0;
void prefix(int pi[])
{
int k = 0;
pi[1] = 0;
for(int i = 2; i <= N; i++)
{
while(k > 0 && A[k] != A[i - 1])
k = pi[k];
if(A[k] == A[i - 1])
k++;
pi[i] = k;
}
}
int KMP(char *A, char *B)
{
int pi[N], q = 0;
prefix(pi);
for(int i = 1; i <= M; i++)
{
while(q > 0 && A[q] != B[i - 1])
q = pi[q];
if(A[q] == B[i - 1])
q++;
if(q == N)
match[++nr] = i - N;
}
return nr;
}
int main()
{
f.getline(A, DIM);
N = f.gcount() - 1;
f.getline(B, DIM);
M = f.gcount() - 1;
int ap = KMP(A, B);
g << ap << '\n';
for(int i = 1; i <= ap && i <= 1000; i++)
g << match[i] << ' ';
return 0;
}