Pagini recente » Cod sursa (job #2550467) | Cod sursa (job #1178245) | Cod sursa (job #1576470) | Cod sursa (job #2241899) | Cod sursa (job #283542)
Cod sursa(job #283542)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000015
int N, M, cnt;
char A[MAX_N], B[MAX_N];
int P[MAX_N];
int S[1024];
void read() {
scanf("%s", A);
N = strlen(A);
scanf("%s", B);
M = strlen(B);
}
void prefix() {
int k = 0;
P[1] = 0;
for (int i = 2; i <= N; ++i) {
while (k > 0 && A[i - 1] != A[k])
k = P[k];
if (A[i - 1] == A[k])
++k;
P[i] = k;
}
}
void kmp() {
int k = 0;
for (int i = 1; i <= M; ++i) {
while (k > 0 && B[i - 1] != A[k])
k = P[k];
if (B[i - 1] == A[k])
++k;
if (k == N) {
++cnt;
if (cnt <= 1000)
S[cnt] = i - N;
k = P[k];
}
}
}
void solve() {
prefix();
kmp();
printf("%d\n", cnt);
for (int i = 1; i <= min(cnt, 1000); ++i)
printf("%d ", S[i]);
printf("\n");
}
int main() {
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
read();
solve();
return 0;
}