#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; }