Pagini recente » Cod sursa (job #602938) | Cod sursa (job #2765984) | Arhiva de probleme | Cod sursa (job #3202025) | Cod sursa (job #3288362)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
auto getPi(const string &str) {
vector<int> pi(str.size());
int k = 0;
for (int i = 1; i < int(str.size()); i++) {
while (k && str[i] != str[k])
k = pi[k - 1];
if (str[i] == str[k])
k++;
pi[i] = k;
}
return pi;
}
auto kmp(const string &str, const string &pat) {
const string concat = pat + '#' + str;
auto pi = getPi(concat);
vector<int> occ;
for (int i = pat.size() + 1; i < int(concat.size()); i++)
if (pi[i] == int(pat.size()))
occ.push_back(i - 2 * int(pat.size()));
return occ;
}
int main() {
fin >> t >> s;
auto occ = kmp(s, t);
fout << occ.size() << '\n';
for (int i = 0; i < occ.size() && i < 1000; i++) {
fout << occ[i] << ' ';
}
return 0;
}