Pagini recente » Rezultatele filtrării | Cod sursa (job #227361) | Cod sursa (job #2346364) | Cod sursa (job #1408382) | Cod sursa (job #2725896)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
class Result {
public:
void AddMatch(int pos);
friend ostream& operator<<(ostream& os, const Result& res);
private:
vector<int> matches_;
int match_count_ = 0;
};
void Result::AddMatch(int pos) {
if (matches_.size() < 1000) {
matches_.push_back(pos);
}
match_count_ += 1;
}
ostream& operator<<(ostream& os, const Result& res) {
os << res.match_count_ << "\n";
for (const auto& pos : res.matches_) {
os << pos << " ";
}
os << "\n";
return os;
}
vector<int> Prefix(const string& str) {
vector<int> prefix(str.size(), 0);
auto index = 0;
for (size_t i = 1; i < str.size(); i += 1) {
while (index > 0 && str[i] != str[index]) {
index = prefix[index - 1];
}
if (str[i] == str[index]) {
index += 1;
}
prefix[i] = index;
}
return prefix;
}
Result Solve(const string& needle, const string& haystack) {
auto prefix = Prefix(needle);
Result res;
auto index = 0;
for (size_t i = 0; i < haystack.size(); i += 1) {
while (index > 0 && needle[index] != haystack[i]) {
index = prefix[index - 1];
}
if (needle[index] == haystack[i]) {
index += 1;
}
if (index >= (int)needle.size()) {
res.AddMatch(i + 1 - needle.size());
index = prefix[index - 1];
}
}
return res;
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string needle, haystack;
getline(fin, needle);
getline(fin, haystack);
auto res = Solve(needle, haystack);
fout << res << "\n";
return 0;
}