Pagini recente » Cod sursa (job #2495924) | Cod sursa (job #1240672) | Cod sursa (job #89162) | Cod sursa (job #2807341) | Cod sursa (job #2717161)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector < int > kmp(const string& s, const string& pattern) {
vector < int > pi(pattern.size() + 5, 0);
vector < int > occurrences;
for(int i{2}, k{}; i < pattern.size();++i) {
for(;k && pattern[k + 1] != pattern[i];)
k = pi[k];
if(pattern[k + 1] == pattern[i])
k++;
pi[i] = k;
}
for(int i{1}, k{};i < s.size();++i) {
for(;k && pattern[k + 1] != s[i];)
k = pi[k];
if(pattern[k + 1] == s[i])
k++;
if(k == pattern.size() - 1) {
occurrences.push_back(i - pattern.size() + 1);
if(occurrences.size() >= 1000)
return occurrences;
}
}
return occurrences;
}
int main() {
string s, pattern;
f >> pattern >> s;
s = " " + s;
pattern = " " + pattern;
auto sol = kmp(s, pattern);
g << sol.size() << '\n';
for(auto& it : sol)
g << it << ' ';
return 0;
}