Pagini recente » Cod sursa (job #1005720) | Cod sursa (job #2811045) | Cod sursa (job #22602) | Cod sursa (job #2045417)
#include <bits/stdc++.h>
using namespace std;
vector<int> ComputePi(string s) {
int n = s.size();
vector<int> pi(n + 1, -1);
for (int i = 0; i < n; ++i) {
int j = pi[i];
while (j != -1 && s[j] != s[i]) j = pi[j];
pi[i + 1] = j + 1;
}
return pi;
}
vector<int> Match(string text, string pat) {
auto pi = ComputePi(pat);
vector<int> ret;
int j = 0;
for (int i = 0; i < (int)text.size(); ++i) {
while (j != -1 && pat[j] != text[i]) j = pi[j];
if (++j == pat.size())
ret.push_back(i), j = pi[j];
}
return ret;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string text, pat; cin >> pat >> text;
auto matches = Match(text, pat);
cout << matches.size() << endl;
for (int i = 0; i < (int)matches.size() && i < 1000; ++i)
cout << matches[i] - pat.size() + 1 << " ";
cout << endl;
}