Pagini recente » Cod sursa (job #2329589) | Cod sursa (job #2436961) | Cod sursa (job #1928402) | Cod sursa (job #2148060) | Cod sursa (job #1751964)
#include <fstream>
#include <algorithm>
using namespace std;
class StringMatcher {
public:
StringMatcher(string const &s):
pattern(s) {
sufPref = vector<int>(pattern.size());
sufPref[0] = 0;
for(int i = 1, match = 0; i < pattern.size(); i++) {
while(match > 0 && pattern[match] != pattern[i]) {
match = sufPref[match - 1];
}
if(pattern[match] == pattern[i]) {
match++;
}
sufPref[i] = match;
}
}
vector<int> findOccurrences(string const& _template) {
vector<int> _templateSufPref = matchString(_template);
vector<int> oc;
for(int i = 0; i < _template.size(); i++) {
if(_templateSufPref[i] == pattern.size()) {
oc.push_back(i - pattern.size() + 1);
}
}
if(oc.size() > 1000) {
oc.erase(oc.begin() + 1000, oc.end());
}
return oc;
}
private:
vector<int> matchString(string const& _template) {
vector<int> _templateSufPref(_template.size());
for(int i = 0, match = 0; i < _template.size(); i++) {
while(match > 0 && pattern[match] != _template[i]) {
match = sufPref[match - 1];
}
if(pattern[match] == _template[i]) {
match++;
}
_templateSufPref[i] = match;
}
return _templateSufPref;
}
vector<int> sufPref;
string pattern;
};
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern, _template;
f >> pattern >> _template;
vector<int> oc = StringMatcher(pattern).findOccurrences(_template);
g << oc.size() << "\n";
for(auto o : oc) g << o << " ";
g << "\n";
return 0;
}