Pagini recente » Cod sursa (job #1319879) | Cod sursa (job #2818327) | Cod sursa (job #2189039) | Cod sursa (job #3169920) | Cod sursa (job #3157197)
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "strmatch";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
vector<int> computeLPS(const string &s) {
vector<int> lps(s.size());
int j = 0;
for (int i = 1; i < (int)s.size();) {
if (s[i] == s[j]) {
lps[i] = j + 1;
j++, i++;
} else {
if (j != 0) {
j = lps[j - 1];
} else {
lps[i] = 0;
i++;
}
}
}//*/
return lps;
}
vector<int> computeKMP(const string &text, const string &pat) {
vector<int> lps = computeLPS(pat), ans;
size_t i = 0, j = 0;
while (i < text.size()) {
if (text[i] == pat[j]) {
i++, j++;
} else {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
if (j == pat.size()) {
ans.push_back(i - j);
j = j == 0 ? 0 : lps[j - 1];
}
}
return ans;
}
int main() {
string pat, text;
getline(fin, pat);
getline(fin, text);
vector<int> ans = computeKMP(text, pat);
fout << ans.size() << endl;
for (int x : ans) {
fout << x << ' ';
}
fout << endl;
return 0;
}