Pagini recente » Cod sursa (job #1751431) | Cod sursa (job #742302)
Cod sursa(job #742302)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> prefix(const string &subject) {
vector<int> pi(subject.size(), 0);
// Ignore the first char because from there we match the whole string
size_t matchTo = 0;
for (size_t i = 1; i < subject.size(); ++i) {
while (matchTo > 0 && subject[i] != subject[matchTo])
matchTo = pi[matchTo - 1];
if (subject[i] == subject[matchTo])
++matchTo;
pi[i] = matchTo;
}
return pi;
}
vector<int> kmp(const string &pattern, const string &subject) {
vector<int> pi = prefix(pattern);
vector<int> matches;
size_t matchTo = 0;
for (size_t i = 0; i < subject.size(); ++i) {
while (matchTo > 0 && subject[i] != pattern[matchTo])
matchTo = pi[matchTo - 1];
if (subject[i] == pattern[matchTo])
++matchTo;
if (matchTo == pattern.size())
matches.push_back(i - pattern.size() + 1);
}
return matches;
}
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string A, B;
cin >> A >> B;
vector<int> answer = kmp(A, B);
cout << answer.size() << "\n";
for (int i = 0; i < min(static_cast<int>(answer.size()), 1000); ++i)
cout << answer[i] << " ";
cout << "\n";
}