Pagini recente » Cod sursa (job #1045789) | Cod sursa (job #2606073) | Cod sursa (job #1253481) | Cod sursa (job #924981) | Cod sursa (job #2150717)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
constexpr int kMaxCount = 1000;
vector<int> CalcPrefix(const string &a)
{
vector<int> prefix(a.size(), 0);
int ind = 0;
for (size_t i = 1; i < a.size(); ++i) {
while (ind > 0 && a[i] != a[ind]) {
ind = prefix[ind - 1];
}
if (a[i] == a[ind]) {
ind += 1;
}
prefix[i] = ind;
}
return prefix;
}
pair<int, vector<int>> Solve(const string &a, const string &b)
{
vector<int> matches;
int match_count = 0;
auto prefix = CalcPrefix(a);
int ind = 0;
for (size_t i = 0; i < b.size(); ++i) {
while (ind > 0 && b[i] != a[ind]) {
ind = prefix[ind - 1];
}
if (b[i] == a[ind]) {
ind += 1;
}
if (ind == (int)a.size()) {
match_count += 1;
if (match_count <= kMaxCount) {
matches.push_back(i - a.size() + 1);
}
}
}
return {match_count, matches};
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
getline(fin, a);
getline(fin, b);
auto res = Solve(a, b);
fout << res.first << "\n";
for (const auto &elem : res.second) {
fout << elem << " ";
}
fout << "\n";
return 0;
}