rabinKarp() (ラビンカープ法, RollingHashを用いた文字列検索 $O(|s|)$)
(String/rabin-karp.hpp)

#pragma once

#include <cstdint>
#include <vector>
#include "./rolling-hash.hpp"

/**
 * @brief rabinKarp() (ラビンカープ法, RollingHashを用いた文字列検索 $O(|s|)$)
 * s の中で pattern が出現するインデックスを全て求めて vector として返す(インデックスは昇順)。
 */
template <uint_fast64_t Base>
std::vector<size_t> rabinKarp(const RollingHash<Base>& s, const RollingHash<Base>& pattern) {
    const auto sLen = s.size();
    const auto patLen = pattern.size();

    std::vector<size_t> foundIndexes;
    foundIndexes.reserve(sLen);

    for (size_t i = 0; i + patLen <= sLen; ++i) {
        if (s.substr(i, patLen) == pattern.hash()) foundIndexes.emplace_back(i);
    }

    foundIndexes.shrink_to_fit();
    return foundIndexes;
}

#line 2 "String/rabin-karp.hpp"

#include <cstdint>
#include <vector>
#line 2 "String/rolling-hash.hpp"

#include <cassert>
#include <string>
#line 6 "String/rolling-hash.hpp"
#include <functional>

/**
 * @brief Rolling-Hash (ローリングハッシュ, mod値 $2^{61} - 1$ 固定)
 * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 */
template <uint_fast64_t Base>
class RollingHash {
public:
    using u64 = uint_fast64_t;
    using u128 = __uint128_t;
    static constexpr u64 MOD = (1uL << 61) - 1;
    static constexpr u64 BASE = Base;

private:
    std::vector<u64> m_hash;

public:
    RollingHash() = default;

    template <class InputIter>
    RollingHash(InputIter begin, InputIter end)
        : m_hash(std::distance(begin, end) + 1, 0) {
        if (powArray().empty()) {
            powArray().reserve(1e6);
            powArray().emplace_back(1);
        }
        growPowArray(m_hash.size());

        size_t i;
        InputIter itr;
        for (itr = begin, i = 0; itr != end; ++itr, ++i) {
            m_hash[i + 1] = add(mul(m_hash[i], BASE), *itr);
        }
    }

    //! 文字列全体のハッシュ値
    u64 hash() const { return m_hash.back(); }

    //! 半開区間 [l, r) のハッシュ値
    u64 rangeHash(size_t l, size_t r) const {
        assert(l < r && r < m_hash.size());
        return add(m_hash[r], MOD - mul(m_hash[l], powArray()[r - l]));
    }

    //! rangeHash(begin, begin + length) と等価
    u64 substr(size_t begin, size_t length) const { return rangeHash(begin, begin + length); }

    //! もとの文字列の長さ
    size_t size() const { return m_hash.size() - 1; }

    //! 連結した文字列 (leftStr + rightStr) のハッシュ値
    static u64 concat(u64 leftHash, u64 rightHash, size_t rightLength) {
        growPowArray(rightLength);
        return add(mul(leftHash, powArray()[rightLength]), rightHash);
    }

private:
    static inline std::vector<u64>& powArray() {
        static std::vector<u64> p;
        return p;
    }

    static constexpr inline u64 add(u64 a, u64 b) noexcept {
        if ((a += b) >= MOD) a -= MOD;
        return a;
    }

    static constexpr inline u64 mul(u128 a, u128 b) noexcept {
        const auto c = a * b;
        return add(static_cast<u64>(c >> 61), static_cast<u64>(c & MOD));
    }

    static inline void growPowArray(size_t len) {
        ++len;
        while (powArray().size() < len) {
            powArray().emplace_back(mul(powArray().back(), BASE));
        }
    }
};
#line 6 "String/rabin-karp.hpp"

/**
 * @brief rabinKarp() (ラビンカープ法, RollingHashを用いた文字列検索 $O(|s|)$)
 * s の中で pattern が出現するインデックスを全て求めて vector として返す(インデックスは昇順)。
 */
template <uint_fast64_t Base>
std::vector<size_t> rabinKarp(const RollingHash<Base>& s, const RollingHash<Base>& pattern) {
    const auto sLen = s.size();
    const auto patLen = pattern.size();

    std::vector<size_t> foundIndexes;
    foundIndexes.reserve(sLen);

    for (size_t i = 0; i + patLen <= sLen; ++i) {
        if (s.substr(i, patLen) == pattern.hash()) foundIndexes.emplace_back(i);
    }

    foundIndexes.shrink_to_fit();
    return foundIndexes;
}