Pagini recente » Cod sursa (job #3187595) | Cod sursa (job #1568002) | Cod sursa (job #2958897) | Cod sursa (job #1373358) | Cod sursa (job #1809030)
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
class KMP {
public:
KMP(const string& text) : text_(text) {}
pair<int, vector<int>> GetMatchingIndexes(const string& pattern, int max_index_count) {
int count = 0;
vector<int> indexes;
indexes.reserve(max_index_count);
vector<int> pi(pattern.size(), 0);
BuildPi(pattern, pi);
int q = 0;
for (int i = 0; i < (int)text_.size(); i++) {
while (q && pattern[q] != text_[i]) {
q = pi[q - 1];
}
if (pattern[q] == text_[i]) {
q++;
}
if (q == (int)pattern.size()) {
if (++count <= max_index_count) {
indexes.push_back(i - pattern.size() + 1);
}
}
}
return {count, indexes};
}
private:
string text_;
void BuildPi(const string& pattern, vector<int>& pi) {
int q = 0;
for (int i = 1; i < (int)pattern.size(); i++) {
while (q && pattern[q] != pattern[i]) {
q = pi[q - 1];
}
if (pattern[q] == pattern[i]) {
q++;
}
pi[i] = q;
}
}
};
int main() {
cin.sync_with_stdio(false);
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pattern;
cin >> pattern;
string text;
cin >> text;
KMP kmp(text);
pair<int, vector<int>> answer = kmp.GetMatchingIndexes(pattern, 1000);
cout << answer.first << '\n';
for (int it : answer.second) {
cout << it << " ";
}
return 0;
}