Pagini recente » Cod sursa (job #2874054) | Cod sursa (job #2475231) | Cod sursa (job #1566471) | Cod sursa (job #467734) | Cod sursa (job #3287558)
// https://www.infoarena.ro/problema/strmatch
#include <array>
#include <iostream>
#include <fstream>
#include <vector>
#define ALG 1
#if ALG == 1
/**
* @brief KMP algorithm, finds max 1000 occurences of a in b.
* next[i] represents the longest prefix of a that is a suffix of a_i
*
* Complexity: O(A+B) time, O(A+B) space
*/
auto strmatch(const std::string& a, const std::string& b)
-> std::pair<int, std::array<int, 1000>>
{
// precompute next array
std::vector<int> next(a.size());
next[0] = -1;
for (int i = 1, k = -1; i < a.size(); ++i) {
// if the prefix cannot be extended to match the current suffix,
// go back to next[k], ensuring that the prexix of a_k is still a
// suffix of a_{i-1} (because a_k was already a suffix of a_{i-1})
while (k >= 0 && a[k + 1] != a[i])
k = next[k];
// extend the prefix
if (a[k + 1] == a[i])
++k;
next[i] = k;
}
// KMP pattern matching - same algorithm as for precomputing the next array
std::array<int, 1000> positions;
int len = 0;
for (int i = 0, q = 0; i < b.size(); ++i) {
// if the prefix cannot be extended to match the current character in b,
// go back to next[q], ensuring that the prefix of a_q is still a
// suffix to b_{i-1} (because the next[q] step guarantees that a_next[q]
// will be a suffix of a_q, and thus b_i by transitivity)
while (q >= 0 && a[q + 1] != b[i])
q = next[q];
// extend the match
if (a[q + 1] == b[i])
++q;
// found a full match
if (q == a.size() - 1) {
positions[len++] = i - a.size() + 1;
if (len >= 1000)
break;
}
}
return { len, std::move(positions) };
}
#endif
int main()
{
try {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::string a, b;
in >> a >> b;
auto [len, positions] = strmatch(a, b);
out << len << '\n';
for (int i = 0; i < len; ++i)
out << positions[i] << ' ';
}
catch (const std::exception& e) {
std::cerr << e.what();
return EXIT_FAILURE;
}
}