Pagini recente » Cod sursa (job #1508038) | Cod sursa (job #558260) | Cod sursa (job #2349197) | Cod sursa (job #1164116) | Cod sursa (job #2884350)
#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;
// for char in pattern
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);
kmp();
cout << res.size() << endl;
for (int &k : res) cout << k << ' ';
}