Pagini recente » Cod sursa (job #1132451) | Rating Mihai Truta (miketheboss) | Cod sursa (job #106885) | Cod sursa (job #143707) | Cod sursa (job #282789)
Cod sursa(job #282789)
#include <fstream>
#include <cstring>
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[MAX_N];
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) {
S[++cnt] = i - N;
k = P[k];
}
}
}
void solve() {
prefix();
kmp();
printf("%d\n", cnt);
for (int i = 1; i <= cnt; ++i)
printf("%d ", S[i]);
printf("\n");
}
int main() {
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
read();
solve();
return 0;
}