Pagini recente » Cod sursa (job #926740) | Cod sursa (job #1257075) | Cod sursa (job #1232398) | Cod sursa (job #1107640) | Cod sursa (job #1145530)
#include <stdio.h>
#include <string.h>
#include <queue>
#define NMAX 2000005
using namespace std;
char A[NMAX], B[NMAX];
int L[NMAX];
queue <int> q;
void prefix() {
int k, p;
int m = strlen(A);
L[1] = 0;
for (p = 2; p <= m; ++p) {
k = L[p-1];
while (k > 0 && A[k+1] != A[p])
k = L[k];
if (A[k+1] == A[p])
++k;
L[p] = k;
}
//for (int i = 1; i < m; ++i)
// printf ("%d ", L[i]);
}
void kmp() {
int k, t, m, n, count = 0;
m = strlen(A) - 1;
n = strlen(B) - 1;
k = 0;
for (t = 1; t <= n; ++t) {
while (k > 0 && A[k+1] != B[t])
k = L[k];
if (A[k+1] == B[t])
++k;
if (k == m) {
++count;
if (count <= 1000)
q.push(t-m);
k = L[k];
}
}
printf ("%d\n", count);
while (!q.empty()) {
printf ("%d ", q.front());
q.pop();
}
printf ("\n");
}
int main() {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
int m, i;
scanf ("%s %s", A, B);
m = strlen(A);
for (i = m; i >= 1; --i)
A[i] = A[i-1];
m = strlen(B);
for (i = m; i >= 1; --i)
B[i] = B[i-1];
prefix();
kmp();
return 0;
}