Cod sursa(job #3287558)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 18 martie 2025 16:14:05
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
// 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;
    }
}