Pagini recente » Cod sursa (job #650944) | Cod sursa (job #2921890) | Cod sursa (job #1690187) | Cod sursa (job #2874005) | Cod sursa (job #2974840)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif
const int NMAX = 2e6+5;
int n, m;
char a[NMAX], b[NMAX];
int lps[NMAX];
vector<int> ans;
void read() {
fin >> b >> a;
n = strlen(a);
m = strlen(b);
}
void precalc() {
int j = 0;
for (int i = 1; i < m; i++) {
if (b[i] == b[j]) {
lps[i] = ++j;
} else {
if (j == 0) {
lps[i] = 0;
} else {
j = lps[j - 1];
i--;
}
}
}
}
void solve() {
for (int i = 0, j = 0; i < n; i++) {
if (a[i] == b[j]) {
j++;
if (j == m) {
j = lps[j - 1];
ans.push_back(i - m + 1);
}
} else {
if (j == 0) continue;
j = lps[j - 1];
i--;
}
}
fout << ans.size() << endl;
for (auto &it : ans)
fout << it << ' ';
}
int main() {
read();
precalc();
solve();
return 0;
}