Pagini recente » Cod sursa (job #1132871) | Rating Alexa Geo (Alexa_Geo) | Cod sursa (job #1990254) | Cod sursa (job #94554) | Cod sursa (job #2266725)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector<size_t> GetZFunc(const string &str)
{
vector<size_t> zfunc(str.size(), 0);
size_t left = 0, right = 0;
for (size_t i = 1; i < str.size(); i += 1) {
if (i <= right) {
zfunc[i] = min(zfunc[i - left], right - i + 1);
}
while (i + zfunc[i] < str.size()) {
if (str[i + zfunc[i]] != str[zfunc[i]]) {
break;
}
zfunc[i] += 1;
}
if (i + zfunc[i] - 1 >= right) {
left = i;
right = i + zfunc[i] - 1;
}
}
return zfunc;
}
pair<int, vector<int>> FindMatches(const string &pattern, const string &text)
{
auto str = pattern + "#" + text;
auto zfunc = GetZFunc(str);
constexpr auto kMaxMatches = 1000;
vector<int> matches;
auto match_count = 0;
for (size_t i = pattern.size(); i < str.size(); i += 1) {
if (zfunc[i] >= pattern.size()) {
match_count += 1;
if (match_count <= kMaxMatches) {
matches.push_back(i - pattern.size() - 1);
}
}
}
return {match_count, matches};
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, text;
getline(fin, pattern);
getline(fin, text);
auto res = FindMatches(pattern, text);
fout << res.first << "\n";
for (const auto &pos : res.second) {
fout << pos << " ";
}
fout << "\n";
return 0;
}