Pagini recente » Cod sursa (job #767) | Cod sursa (job #1748503) | Cod sursa (job #2687006) | Cod sursa (job #2392685) | Cod sursa (job #605963)
Cod sursa(job #605963)
//============================================================================
// Name : KMP.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define MAXN 2000010
#define pb push_back
char a[MAXN], b[MAXN];
int N,M;
int pi[MAXN];
vector<int> solve;
void make_prefix() {
int k = -1, i;
for (i = 1, pi[0] = -1; i < N; i++) {
while (k >= 0 && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
k++;
pi[i] = k;
}
}
void KMP() {
int k = -1, i;
for (i = 0; i < M; i++) {
while (k >= 0 && a[k + 1] != b[i])
k = pi[k];
if (a[k + 1] == b[i])
k++;
if (k == N - 1)
solve.pb(i - N + 1);
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a, sizeof(b), stdin);
fgets(b, sizeof(b), stdin);
for (; (a[N] >= 'A' && a[N] <= 'Z') || (a[N] >= 'a' && a[N] <= 'z') || (a[N] >= '0' && a[N] <= '9'); ++N);
for (; (b[M] >= 'A' && b[M] <= 'Z') || (b[M] >= 'a' && b[M] <= 'z') || (b[M] >= '0' && b[M] <= '9'); ++M);
make_prefix();
KMP();
printf("%d\n", solve.size());
for (unsigned i = 0 ; i < solve.size() && i < 1000; i++)
printf("%d ", solve[i]);
return 0;
}