Pagini recente » Cod sursa (job #1383354) | Cod sursa (job #2990355) | Cod sursa (job #1159762) | Cod sursa (job #1413481) | Cod sursa (job #1492102)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
vector<int> kmp(const string& p, const string& t) {
vector<int> matches;
vector<int> a(p.size());
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((int)i + 1 - p.size());
j = a[j - 1];
}
}
return matches;
}
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);
cout << ans.size() << "\n";
int k = 0;
for (auto& x : ans) {
cout << x << " ";
if (k == 1000) break;
}
}