Pagini recente » Borderou de evaluare (job #1359312) | Borderou de evaluare (job #2554146) | Borderou de evaluare (job #1394623) | Borderou de evaluare (job #1868114) | Cod sursa (job #1751948)
#include <fstream>
#include <algorithm>
using namespace std;
class StringMatcher {
public:
StringMatcher(string const &s):
pattern(s) {
sufPref = vector<int>(pattern.size());
sufPref[0] = -1;
for(int i = 1, match = -1; i < pattern.size(); i++) {
while(match > -1 && pattern[match + 1] != pattern[i]) {
match = sufPref[match];
}
match += (pattern[match + 1] == pattern[i]);
sufPref[i] = match;
}
}
vector<int> matchString(string const& _template) {
vector<int> _templateSufPref(_template.size());
for(int i = 0, match = -1; i < _template.size(); i++) {
while(match > -1 && pattern[match + 1] != _template[i]) {
match = sufPref[match];
}
match += (pattern[match + 1] == _template[i]);
_templateSufPref[i] = match;
}
return _templateSufPref;
}
private:
vector<int> sufPref;
string pattern;
};
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern;
string _template;
f >> pattern >> _template;
vector<int> sufPref = StringMatcher(pattern).matchString(_template);
vector<int> occ;
for(int i = 0; i < _template.size() - pattern.size(); i++) {
if(sufPref[i + pattern.size() - 1] + 1 == pattern.size()) {
occ.push_back(i);
}
}
g << occ.size() << "\n";
for(int i = 0; i <= min(1000, (int)occ.size() - 1); i++) g << occ[i] << " ";
g << "\n";
return 0;
}