Pagini recente » Cod sursa (job #1672000) | Cod sursa (job #3272397) | Cod sursa (job #3171173) | Cod sursa (job #2459404) | Cod sursa (job #1789777)
#include <stdio.h>
#include <cstring>
#include <vector>
#define maxdim 2000005
using namespace std;
int n, m;
int pi[maxdim];
char A[maxdim], B[maxdim];
vector<int> sol;
inline void prefix() {
int k = 0;
for (int i = 2; i <= n; ++i) {
while (k > 0 && A[k + 1] != A[i]) {
k = pi[k];
}
if (A[k + 1] == A[i]) {
++k;
}
pi[i] = k;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", A + 1, B + 1);
n = strlen(A + 1);
m = strlen(B + 1);
prefix();
int matches = 0;
int k = 0;
for (int i = 1; i <= m; ++i) {
while (k > 0 && B[i] != A[k + 1]) {
k = pi[k];
}
if (B[i] == A[k + 1]) {
++k;
}
if (k == n) {
++matches;
if (matches <= 1000) {
sol.push_back(i - n);
}
}
}
printf("%d\n", matches);
for (int match : sol) {
printf("%d ", match);
}
printf("\n");
return 0;
}