test/AOJ/ALDS1_14_B-String-Search.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>
#include <string>
#include <vector>

#include "../../String/rolling-hash.hpp"
#include "../../String/rabin-karp.hpp"
#include "../../Util/IO/println.hpp"
#include "../../Util/all-macro.hpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    using RH = RollingHash<17273747>;

    std::string T, P;
    std::cin >> T >> P;

    const RH rolHashT(all(T));
    const RH rolHashP(all(P));

    for (const auto foundIndex : rabinKarp(rolHashT, rolHashP)) {
        println(foundIndex);
    }

    return 0;
}

#line 1 "test/AOJ/ALDS1_14_B-String-Search.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>
#include <string>
#include <vector>

#line 2 "String/rolling-hash.hpp"

#include <cassert>
#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 2 "String/rabin-karp.hpp"

#include <cstdint>
#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;
}
#line 3 "Util/IO/println.hpp"
#include <utility>

/**
 * @brief println() (可変個の値を空白区切りで出力して改行する)
 */
inline void println() {
    std::cout << '\n';
}
template <class Head, class... Tail>
inline void println(Head&& head, Tail&&... tail) {
    std::cout << head << &" "[!sizeof...(tail)];
    println(std::forward<Tail>(tail)...);
}
#line 2 "Util/all-macro.hpp"

/**
 * @brief all()マクロ
 */
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
#line 11 "test/AOJ/ALDS1_14_B-String-Search.test.cpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    using RH = RollingHash<17273747>;

    std::string T, P;
    std::cin >> T >> P;

    const RH rolHashT(all(T));
    const RH rolHashP(all(P));

    for (const auto foundIndex : rabinKarp(rolHashT, rolHashP)) {
        println(foundIndex);
    }

    return 0;
}