Pagini recente » Cod sursa (job #144817) | Cod sursa (job #2039493) | Cod sursa (job #1212794) | Cod sursa (job #2176371) | Cod sursa (job #2063177)
#include <fstream>
#include <vector>
using std::string; using std::vector;
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
string toMatch, matchIn;
vector<int> KMP(string input, string substr);
int main() {
in >> toMatch >> matchIn;
vector<int> locations = KMP(matchIn, toMatch);
out << locations.size() << '\n';
for (int i = 0; i < locations.size() && i < 1000; ++i) {
out << locations[i] << ' ';
}
return 0;
}
vector<int> KMP(string input, string substr) {
vector<int> positions(substr.size() + 1, -1);
vector<int> result;
for (unsigned int i = 1; i <= substr.size(); i++) {
int pos = positions.at(i - 1);
while (pos != -1 && substr[pos] != substr[i - 1]) pos = positions.at(pos);
positions.at(i) = pos + 1;
}
int pos_input = 0, pos_substr = 0;
while (pos_input < input.size()) {
while (pos_substr != -1 && (substr[pos_substr] != input[pos_input] || pos_substr == substr.size())) pos_substr = positions.at(pos_substr);
pos_substr++;
pos_input++;
if (pos_substr == substr.size()) result.push_back(pos_input - pos_substr);
}
return result;
}