Pagini recente » Cod sursa (job #3142550) | Cod sursa (job #3169897) | Cod sursa (job #3141857) | Cod sursa (job #2818319) | Cod sursa (job #3157203)
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "strmatch";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
constexpr size_t MAX_ANS = 1000;
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;
const size_t n = text.size(), m = pat.size();
size_t i = 0, j = 0;
while (n - i >= m - j) {
if (text[i] == pat[j]) {
i++, j++;
}
if (j == m) {
if (ans.size() < MAX_ANS) {
ans.push_back(i - j);
}
j = lps[j - 1];
} else if (i < n && text[i] != pat[j]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return ans;
}
int main() {
string pat, text;
getline(fin, pat);
getline(fin, text);
vector<int> ans = computeKMP(text, pat);
fout << min(MAX_ANS, ans.size()) << endl;
for (int x : ans) {
fout << x << ' ';
}
fout << endl;
return 0;
}