Pagini recente » Cod sursa (job #1152083) | Cod sursa (job #2686441) | Cod sursa (job #2312142) | Cod sursa (job #1909756) | Cod sursa (job #2884358)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
static const int nmax = 2e6 + 2;
static char txt[nmax], pat[nmax];
static int n, m, lps[nmax];
vector<int> res;
void computeLPS() {
int len = 0, i = 1;
while (i < m) {
if (pat[len] == pat[i]) {
lps[i++] = ++len;
continue;
}
if (len) len = lps[len - 1];
else i++;
}
}
void kmpSearch() {
int i = 0, j = 0; // txt & pat
while (i < n) {
if (txt[i] == pat[j]) i++, j++;
if (j == m) res.push_back(i - m), j = lps[j - 1];
else if (i < n && txt[i] != pat[j]) {
if (j) j = lps[j - 1];
else i++;
}
}
}
void kmp() {
computeLPS();
kmpSearch();
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> pat >> txt;
n = strlen(txt);
m = strlen(pat);
res.reserve(nmax);
kmp();
cout << res.size() << endl;
auto end = min(res.begin() + 1000U, res.end());
for (auto it = res.begin(); it != end; ++it) cout << *it << ' ';
}