Pagini recente » Cod sursa (job #275969) | Cod sursa (job #1124664) | Cod sursa (job #2078409) | Cod sursa (job #1560097) | Cod sursa (job #1818078)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void prefix(const string &sub, vector<int> &pi) {
int curr = 0;
for (size_t i = 2; i < sub.length(); i++) {
while(curr > 0 && sub[i] != sub[curr + 1]) {
curr = pi[curr];
}
if(sub[i] == sub[curr + 1]) {
curr++;
}
pi.push_back(curr);
}
}
void KMP(const string &sub, const string &str, const vector<int> &pi, vector<int> &result) {
int curr = 0;
int sub_length = sub.size();
for (size_t i = 1; i < str.length(); i++) {
while(curr > 0 && sub[curr + 1] != str[i]) {
curr = pi[curr];
}
if(sub[curr + 1] == str[i]) {
curr++;
}
if(curr == sub_length - 1) {
if (result.size() < 1000) {
result.push_back(i - curr + 1);
}
curr = pi[curr];
}
}
}
int main() {
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string in1;
string in2;
string sub = " ";
string str = " ";
in >> in1 >> in2;
sub.append(in1);
str.append(in2);
vector<int> pi(2);
prefix(sub, pi);
vector<int> result;
KMP(sub, str, pi, result);
int count = result.size();
out << count << "\n";
for (int i : result) {
out << i - 1 << " ";
}
return 0;
}