Pagini recente » Cod sursa (job #2208467) | Cod sursa (job #2235588) | Cod sursa (job #1730429) | Cod sursa (job #1390786) | Cod sursa (job #3312541)
#include <bits/stdc++.h>
using namespace std;
vector<int> prefix_function(const string& s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
vector<int> kmp_search(const string& text, const string& pattern) {
string combined = pattern + "#" + text;
vector<int> pi = prefix_function(combined);
vector<int> matches;
int m = pattern.size();
for (int i = m + 1; i < (int)pi.size(); i++) {
if (pi[i] == m) {
matches.push_back(i - 2 * m);
}
}
return matches;
}
int main() {
#ifndef LOCAL
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#endif
string pat, txt;
cin >> pat >> txt;
auto matches = kmp_search(txt, pat);
cout << matches.size() << "\n";
for (int i = 0; i < (int)matches.size(); i++) {
if (i) cout << " ";
cout << matches[i];
}
cout << "\n";
}