Pagini recente » Cod sursa (job #2642002) | Cod sursa (job #66067) | Cod sursa (job #1127085) | Cod sursa (job #127781) | Cod sursa (job #1737676)
#include <bits/stdc++.h>
#define MAXN 2000010
#define pb push_back
using namespace std;
char A[MAXN], B[MAXN];
int n, m, F[MAXN], ans;
vector<int> matches;
void failFunction(char* S, int length) {
int j;
F[0] = F[1];
for (int i = 2; i <= length; ++i) {
j = F[i - 1];
for ( ; ; ) {
if (S[j] == S[i - 1]) {
F[i] = j + 1;
break;
}
if (j == 0) {
F[i] = 0;
break;
}
j = F[j];
}
}
}
void kmp(char* A, int m, char* B, int n, int* F) {
int i = 0, j = 0;
while(1) {
if (j == n) break;
if (A[i] == B[j]) {
++i;
++j;
if (i == m) {
++ans;
matches.pb(j - m);
if (ans == 1000) return;
}
}
else {
if (i == 0) {
++j;
}
else {
i = F[i];
}
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", A, B);
m = strlen(A);
n = strlen(B);
if (m > n) printf("0");
else {
failFunction(A, m);
kmp(A, m, B, n, F);
printf("%d\n", ans);
for (int i = 0; i < matches.size(); ++i)
printf("%d ", matches[i]);
}
return 0;
}