Pagini recente » Cod sursa (job #1376979) | Cod sursa (job #227066) | Cod sursa (job #1760) | Cod sursa (job #2752392) | Cod sursa (job #3298314)
#include <bits/stdc++.h>
#define LEN_MAX (int)2e6 + 5
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int pi[LEN_MAX];
vector<int> sol;
void PrintSol() {
fout << sol.size() << "\n";
for (int idx: sol) {
fout << idx << " ";
}
}
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()) {
if (sol.size() < 1000) {
sol.push_back(i + 1 - A.size());
}
else {
PrintSol();
return 0;
}
idx = pi[idx - 1];
}
}
else {
while (idx != 0 && B[i] != A[idx]) {
idx = pi[idx - 1];
}
if (B[i] == A[idx]) {
idx++;
}
}
}
PrintSol();
return 0;
}