Pagini recente » Cod sursa (job #631692) | Cod sursa (job #1716703) | Cod sursa (job #3221012) | Cod sursa (job #2835926) | Cod sursa (job #2738677)
#include <bits/stdc++.h>
using namespace std;
void DAU(const string &task = "") {
if (!task.empty())
freopen((task + ".in").c_str(), "r", stdin),
freopen((task + ".out").c_str(), "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void PLEC() {
exit(0);
}
const int N(6e6 + 6);
inline void LSP(char *s, int* lsp) {
int j(0);
lsp[0] = 0;
for (size_t i = 1; i < strlen(s); ++i) {
while (j > 0 && s[i] != s[j])
j = lsp[j - 1];
if (s[i] == s[j])
++j;
lsp[i] = j;
}
}
int lsp[N];
inline void KMP(char *text, char *pat) {
int i(0), j(0), nt(static_cast<int>(strlen(text))), np(static_cast<int>(strlen(pat))), cnt(0);
vector<int> res;
LSP(pat, lsp);
while (i < nt) {
if (text[i] == pat[j])
++i, ++j;
else {
if (!j) ++i;
else j = lsp[j - 1];
}
if (j == np) {
++cnt;
if (cnt <= 1000)
res.emplace_back(i - np);
j = lsp[j - 1];
}
}
cout << cnt << '\n';
for (const int &x : res)
cout << x << ' ';
}
char a[N], b[N];
signed main() {
DAU("strmatch");
cin >> a >> b;
KMP(b, a);
PLEC();
}