Pagini recente » Monitorul de evaluare | Cod sursa (job #1028173) | Cod sursa (job #3313512) | Cod sursa (job #1889845) | Cod sursa (job #1614957)
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_N = 2000000;
const int MAX_MATCH = 1000;
char A[MAX_N + 1];
char B[MAX_N + 1];
int pi[MAX_N]; // pi[i] = max(k | s[0..k - 1] = s[i - k + 1.. i]
int match[MAX_MATCH];
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.tie(0);
ios_base::sync_with_stdio(false);
int N, M;
int K;
fin >> A >> B;
N = strlen(A); M = strlen(B);
K = 0;
for (int i = 1; i < N; ++ i) {
while (K > 0 && A[K] != A[i]) {
K = pi[K - 1];
}
if (A[K] == A[i]) {
K++;
}
pi[i] = K;
}
int matches = 0;
K = 0;
for (int i = 0; i < M; ++ i) {
while (K > 0 && A[K] != B[i]) {
K = pi[K - 1];
}
if (A[K] == B[i]) {
K++;
}
if (K == N) {
if (matches < MAX_MATCH) {
match[matches] = i;
}
++ matches;
}
}
fout << matches << '\n'; matches = min(matches, MAX_MATCH);
for (int i = 0; i < matches; ++ i) {
fout << match[i] - N + 1 << " \n"[i == matches - 1];
}
fout.close();
return 0;
}