Pagini recente » Cod sursa (job #1946993) | Cod sursa (job #1435968) | Cod sursa (job #2380909) | Cod sursa (job #2314087) | Cod sursa (job #1548285)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 2e6;
const int kPrint = 1000;
char P[kMaxN + 1], S[kMaxN + 1];
int pi[kMaxN];
int pos[kPrint];
int main(void) {
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int m, n, k, q;
in >> P >> S;
in.close();
m = strlen(P); n = strlen(S);
for (int i = 1; i < m; i++) {
while ((k > 0) && (P[k] != P[i])) {
k = pi[k - 1];
}
if (P[k] == P[i]) {
k++;
}
pi[i] = k;
}
k = 0;
q = 0;
for (int i = 0; i < n; i++) {
while ((k > 0) && (P[k] != S[i])) {
k = pi[k - 1];
}
if (P[k] == S[i]) {
k++;
}
if (k == m) {
if (q < kPrint) {
pos[q] = i - m + 1;
}
q++;
}
}
out << q << '\n';
if (q > kPrint) {
q = kPrint;
}
for (int i = 0; i < q; i++) {
out << pos[i] << ' ';
}
out.close();
return 0;
}