Pagini recente » Cod sursa (job #14852) | Cod sursa (job #2172117) | Cod sursa (job #543731) | Cod sursa (job #443328) | Cod sursa (job #3298319)
#include <bits/stdc++.h>
#define min(a, b) (a < b ? a : b)
#define LEN_MAX (int)2e6 + 5
#define SOL_MAX 1000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int pi[LEN_MAX];
vector<int> sol;
int main() {
fin >> A >> B;
pi[0] = 0;
for (int i = 1; i < A.size(); i++) {
if (A[i] == A[pi[i - 1]]) {
pi[i] = pi[i - 1] + 1;
}
else {
int idx = pi[i - 1];
while (idx != 0 && A[i] != A[idx]) {
idx = pi[idx - 1];
}
if (A[i] == A[idx]) {
idx++;
}
pi[i] = idx;
}
}
int idx = 0;
for (int i = 0; i < B.size(); i++) {
if (idx < A.size() && B[i] == A[idx]) {
idx++;
if (idx == A.size()) {
sol.push_back(i + 1 - A.size());
idx = pi[idx - 1];
}
}
else {
while (idx != 0 && B[i] != A[idx]) {
idx = pi[idx - 1];
}
if (B[i] == A[idx]) {
idx++;
}
}
}
fout << sol.size() << "\n";
for (int i = 0; i < min(SOL_MAX, sol.size()); i++) {
fout << sol[i] << " ";
}
return 0;
}