Pagini recente » Cod sursa (job #492342) | Cod sursa (job #1079796) | Cod sursa (job #734347) | Cod sursa (job #2525234) | Cod sursa (job #2374713)
#include <cassert>
#include <fstream>
#include <string>
#include <vector>
std::fstream fi("strmatch.in", std::ios::in);
std::fstream fo("strmatch.out", std::ios::out);
using result = struct { unsigned cnt = 0; std::vector<unsigned> patfind; };
void patpcomp(std::string const& s, unsigned* pf) {
pf[0] = 0;
for (size_t i = 1, l = 0; i < s.length();)
if (s.at(i) == s.at(l))
pf[i++] = ++l;
else
if (l != 0) l = pf[l - 1];
else pf[i++] = 0;
}
static result kmpratt(std::string const& sa, std::string const& sb, unsigned* pat) {
result res = { 0 };
unsigned m = sa.length(), n = sb.length();
for (size_t i = 0, j = 0; i < n;) {
if (sa.at(j) == sb.at(i)) { i++; j++; }
if (j == m) {
res.patfind.push_back(i - j);
res.cnt++;
j = pat[j - 1];
} else if (i < n && sa.at(j) != sb.at(i)) {
if (j != 0) j = pat[j - 1];
else i++;
}
}
return res;
}
int main (void) {
std::string str1, str2;
assert(std::getline(fi, str1));
assert(std::getline(fi, str2));
unsigned* pattern = new unsigned[str1.length()]; patpcomp(str1, pattern);
result val = kmpratt(str1, str2, pattern);
assert(fo << val.cnt << "\n");
for (const auto& i : val.patfind)
assert(fo << i << " ");
return 0;
}