Pagini recente » Cod sursa (job #705631) | Cod sursa (job #1121435) | Cod sursa (job #1458271) | Cod sursa (job #2104834) | Cod sursa (job #1475419)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 2000505;
const int LIM = 1000;
int n, m, pi[NMAX];
char A[NMAX], B[NMAX];
void read() {
fgets(A + 1, NMAX, stdin);
fgets(B + 1, NMAX, stdin);
n = strlen(A + 1) - 1;
m = strlen(B + 1) - 1;
}
void solve() {
// compute prefix function
for (int i = 2, q = 0; i <= n; i++) {
while (q && A[q + 1] != A[i]) q = pi[q];
if (A[q + 1] == A[i]) q++;
pi[i] = q;
}
// compute matches
int noSol = 0;
vector<int> sol;
for (int i = 1, q = 0; i <= m; i++) {
while (q && A[q + 1] != B[i]) q = pi[q];
if (A[q + 1] == B[i]) q++;
if (q == n) {
noSol++;
if (noSol <= LIM)
sol.push_back(i - n);
q = pi[q];
}
}
printf("%d\n", noSol);
for (size_t i = 0; i < sol.size(); i++) {
if (i > 0) printf(" ");
printf("%d", sol[i]);
}
printf("\n");
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
solve();
return 0;
}