Pagini recente » Cod sursa (job #2171276) | Cod sursa (job #1730433) | Cod sursa (job #1567038) | Cod sursa (job #1344659) | Cod sursa (job #3312540)
#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() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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";
}