Pagini recente » Cod sursa (job #2855804) | Cod sursa (job #1083219) | Cod sursa (job #2815129) | Cod sursa (job #1194560) | Cod sursa (job #1492090)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
vector<int> kmp(const string& p, const string& t, const size_t& matchLimit) {
vector<int> matches;
vector<int> a(p.size() + 1);
size_t j = 0;
for (size_t i = 1; i < p.size(); i++) {
while (p[i] != p[j] && j) j = a[j - 1];
if (p[i] == p[j]) j++;
a[i] = j;
}
for (size_t i = 0; i < t.size(); i++) {
while (t[i] != p[j] && j) j = a[j - 1];
if (t[i] == p[j]) j++;
if (j == p.size()) {
matches.push_back(i - p.size() + 1);
j = a[j - 1];
}
}
return vector<int>(matches.begin(),
matches.begin() + min(matchLimit, matches.size()));
}
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
getline(cin, a);
getline(cin, b);
vector<int> ans = kmp(a, b, 1000);
cout << ans.size() << "\n";
for (auto& x : ans) {
cout << x << " ";
}
}