Pagini recente » Cod sursa (job #2857828) | Cod sursa (job #741919) | Cod sursa (job #1114672) | Cod sursa (job #57137) | Cod sursa (job #605958)
Cod sursa(job #605958)
//============================================================================
// 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(a, sizeof(b), stdin);
for (; (a[M] >= 'A' && a[M] <= 'Z') || (a[M] >= 'a' && a[M] <= 'z') || (a[M] >= '0' && a[M] <= '9'); ++M);
for (; (b[N] >= 'A' && b[N] <= 'Z') || (b[N] >= 'a' && b[N] <= 'z') || (b[N] >= '0' && b[N] <= '9'); ++N);
for (int i = M; i; --i) a[i] = a[i-1]; a[0] = ' ';
for (int i = N; i; --i) b[i] = b[i-1]; b[0] = ' ';
make_prefix();
KMP();
printf("%d\n", solve.size());
for (unsigned i = 0 ; i < solve.size() && i < 1000; i++)
printf("%d ", solve[i]);
return 0;
}