#687643 (C++17) No.430 文字列検索

提出ソース
結果

問題	No.430 文字列検索
ユーザー	naskya
提出日時	2021-08-09 03:08:11
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,230 ms / 2,000 ms
コード長	13,743 bytes
コンパイル時間	794 ms
コンパイル使用メモリ	97,124 KB
実行使用メモリ	24,832 KB
最終ジャッジ日時	2024-11-10 00:57:21
合計ジャッジ時間	13,091 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 5,248 KB
testcase_01	AC	1,230 ms 24,704 KB
testcase_02	AC	1,187 ms 24,704 KB
testcase_03	AC	1,220 ms 24,704 KB
testcase_04	AC	4 ms 5,248 KB
testcase_05	AC	3 ms 5,248 KB
testcase_06	AC	3 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	33 ms 24,704 KB
testcase_09	AC	4 ms 5,248 KB
testcase_10	AC	6 ms 6,528 KB
testcase_11	AC	1,160 ms 24,704 KB
testcase_12	AC	1,115 ms 24,832 KB
testcase_13	AC	1,132 ms 24,832 KB
testcase_14	AC	1,148 ms 24,704 KB
testcase_15	AC	1,124 ms 24,704 KB
testcase_16	AC	1,128 ms 24,704 KB
testcase_17	AC	1,117 ms 24,704 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define ROLLING_HASH_MAX_LENGTH 50000

//! @file rolling_hash.hpp
//! @note The implementation is based on this article https://qiita.com/keymoon/items/11fac5627672a6d6a9f6

#ifndef ROLLING_HASH_HPP
#  define ROLLING_HASH_HPP

#  ifndef ROLLING_HASH_MAX_LENGTH
#    define ROLLING_HASH_MAX_LENGTH 200000
#    define ROLLING_HASH_MAX_LENGTH_not_defined
#  endif

#  include <algorithm>
#  include <array>
#  include <cassert>
#  include <cstdint>
#  include <iostream>
#  include <limits>
#  include <string>
#  include <tuple>
#  include <vector>

#  ifndef O_assert
//! @brief Assert macro
#    define O_assert(...) assert(__VA_ARGS__)
#    define O_assert_not_defined
#  endif

#  ifndef err_and_exit
#    if (CP_LIBRARY_DEBUG_LEVEL >= 2)
//! @brief Print error message and exit
#      define err_and_exit(...) \
        do {                    \
          __VA_ARGS__           \
          O_assert(false);      \
        } while (false)
#    else
#      define err_and_exit(msg) (static_cast<void>(0))
#    endif
#    define err_and_exit_not_defined
#  endif

namespace lib {

namespace internal {
  using u64 = std::uint_least64_t;

  template <unsigned index>
  constexpr u64 mask = (u64(1) << index) - 1;

  template <unsigned index>
  constexpr u64 pad = mask<index>* mask<std::numeric_limits<u64>::digits - index>;

  [[gnu::const]] [[nodiscard]] constexpr u64 mod_mersenne_61(const u64 x) noexcept {
    if (const u64 res = (x >> 61) + (x & mask<61>); res >= mask<61>)
      return res - mask<61>;
    else
      return res;
  }

  [[gnu::const]] [[nodiscard]] constexpr u64 mult(const u64 x, const u64 y) noexcept {
    const u64 x_upper = (x >> 31);
    const u64 x_lower = (x & mask<31>);
    const u64 y_upper = (y >> 31);
    const u64 y_lower = (y & mask<31>);
    const u64 z       = x_upper * y_lower + x_lower * y_upper;
    return ((x_upper * y_upper) << 1) + (z >> 30) + ((z & mask<30>) << 31) + (x_lower * y_lower);
  }

  template <u64 base>
  [[nodiscard]] u64 pow_mod_mersenne_61(unsigned index) {
    static bool first = true;
    static std::array<u64, ROLLING_HASH_MAX_LENGTH + 1> res;

    if (__builtin_expect(first, 0)) {
      first  = false;
      res[0] = 1;
      for (unsigned i = 1; i <= ROLLING_HASH_MAX_LENGTH; ++i)
        res[i] = mod_mersenne_61(mult(res[i - 1], base));
    }

    return res[index];
  }

  template <class TupleType, std::size_t... Is>
  void print_tuple(const TupleType& arg, std::ostream& os, std::index_sequence<Is...>) {
    static_cast<void>(((os << (Is == 0 ? "" : ", "), (os << std::get<Is>(arg))), ...));
  }

  // Using this type alias unables GCC to compile the code for some reason. (no problem with Clang/MSVC. maybe a bug.)
  // template <std::uint32_t... Bases>
  // using hash_t = decltype(std::tuple {(static_cast<u64>(Bases))...});
  // See:  https://wandbox.org/permlink/xpqiYobUkI1EGpgo (on GCC 12.0.0)
  //       https://wandbox.org/permlink/26ZTzuIfTivSz2lR (on Clang 13.0.0)
  // ToDo: Replace decltype(std::tuple {(static_cast<u64>(Bases))...}) with hash_t<Bases...>
  //       and replace decltype(std::tuple {(static_cast<internal::u64>(Bases))...}) with internal::hash_t<Bases...>
  //       when we figure out the workaround or this bug? is fixed.

  template <std::uint32_t... Bases, typename Container, std::size_t... Is>
  void build_hash_sequence_impl(const Container& src,
                                std::vector<decltype(std::tuple {(static_cast<u64>(Bases))...})>& dest,
                                std::index_sequence<Is...>) {
    constexpr std::tuple bases_tuple = std::tuple {Bases...};
    const std::size_t size           = std::size(src);
    auto iter                        = std::cbegin(src);

    for (std::size_t i = 0; i < size; ++iter, ++i)
      static_cast<void>(((std::get<Is>(dest[i + 1]) = mod_mersenne_61(mult(std::get<Is>(dest[i]), std::get<Is>(bases_tuple)) + static_cast<u64>(*iter))), ...));
  }

  template <std::uint32_t... Bases, typename Container>
  [[nodiscard]] std::vector<decltype(std::tuple {(static_cast<u64>(Bases))...})> build_hash_sequence(const Container& src) {
    std::vector<decltype(std::tuple {(static_cast<u64>(Bases))...})> res(std::size(src) + 1);
    build_hash_sequence_impl<Bases...>(src, res, std::make_index_sequence<sizeof...(Bases)> {});
    return res;
  }

  template <std::uint32_t... Bases, std::size_t... Is>
  [[nodiscard]] constexpr decltype(std::tuple {(static_cast<u64>(Bases))...}) substr_hash_impl(const std::vector<decltype(std::tuple {(static_cast<u64>(Bases))...})>& hashes, const int starts, const int length, std::index_sequence<Is...>) {
    constexpr std::tuple bases_tuple = std::tuple {Bases...};
    decltype(std::tuple {(static_cast<u64>(Bases))...}) res;
    static_cast<void>(((std::get<Is>(res) = mod_mersenne_61(std::get<Is>(hashes[starts + length]) + pad<61> - mod_mersenne_61(mult(std::get<Is>(hashes[starts]), pow_mod_mersenne_61<std::get<Is>(bases_tuple)>(length))))), ...));
    return res;
  }

  template <std::uint32_t... Bases>
  [[nodiscard]] constexpr decltype(std::tuple {(static_cast<u64>(Bases))...}) substr_hash(const std::vector<decltype(std::tuple {(static_cast<u64>(Bases))...})>& hashes, const int starts, const int length) {
    return substr_hash_impl<Bases...>(hashes, starts, length, std::make_index_sequence<sizeof...(Bases)> {});
  }

}  // namespace internal

#  if (CP_LIBRARY_DEBUG_LEVEL >= 2)
template <typename Elem, std::uint32_t... Bases>
class rolling_hash {
private:
  std::vector<Elem> src;
  std::vector<decltype(std::tuple {(static_cast<internal::u64>(Bases))...})> hashes;

  struct single_hash {
  private:
    std::vector<Elem> src;
    decltype(std::tuple {(static_cast<internal::u64>(Bases))...}) val;
    int length;

  public:
    constexpr single_hash() noexcept
        : val(), length() {}
    single_hash(const std::vector<Elem>& source, const decltype(std::tuple {(static_cast<internal::u64>(Bases))...})& hash, const int size)
        : src(source), val(hash), length(size) {}
    single_hash(std::vector<Elem>&& source, decltype(std::tuple {(static_cast<internal::u64>(Bases))...})&& hash, const int size)
        : src(std::move(source)), val(std::move(hash)), length(size) {}

    [[nodiscard]] int size() const noexcept {
      return length;
    }

    [[nodiscard]] bool operator==(const single_hash& rhs) const {
      const bool res         = (val == rhs.val);
      const bool precise_res = (src == rhs.src);
      if (__builtin_expect(res != precise_res, 0)) {
        err_and_exit(
          const std::ios_base::fmtflags prev_state = std::cerr.flags();
          std::cerr << "*** Hash collision detected ***\n"
                    << "Hash value: (" << std::hex;
          internal::print_tuple(val, std::cerr, std::make_index_sequence<std::tuple_size_v<decltype(val)>> {});
          std::cerr << ")\n\n";
          std::cerr.flags(prev_state);
          if constexpr (std::is_same_v<char, Elem>) {
            std::cerr << "String 1: \"";
            std::for_each(std::cbegin(src), std::cend(src), [](const char c) { std::cerr << c; });
            std::cerr << "\"\n";
            std::cerr << "String 2: \"";
            std::for_each(std::cbegin(rhs.src), std::cend(rhs.src), [](const char c) { std::cerr << c; });
            std::cerr << "\"\n\n";
          } else {
            std::cerr << "Sequence 1: [ ";
            std::for_each(std::cbegin(src), std::cend(src), [](const Elem& e) { std::cerr << e << ' '; });
            std::cerr << "]\n";
            std::cerr << "Sequence 2: [ ";
            std::for_each(std::cbegin(rhs.src), std::cend(rhs.src), [](const Elem& e) { std::cerr << e << ' '; });
            std::cerr << "]\n\n";
          });
      }
      return res;
    }

    [[nodiscard]] bool operator!=(const single_hash& rhs) const {
      return !(*this == rhs);
    }

    [[nodiscard]] auto hash_value() const noexcept {
      return val;
    }

    void debug_print(const std::string& name = "", std::ostream& os = std::cerr) const {
      if (!name.empty())
        os << name << ": ";

      if constexpr (std::is_same_v<char, Elem>) {
        os << "    String = \"";
        std::for_each(std::cbegin(src), std::cend(src), [&](const char c) { os << c; });
        os << "\"\n";
      } else {
        os << "  Sequence = [ ";
        std::for_each(std::cbegin(src), std::cend(src), [&](const Elem& e) { os << e << ' '; });
        os << "]\n";
      }

      const std::ios_base::fmtflags prev_state = os.flags();
      os << (name.empty() ? std::string() : std::string(std::size(name) + 2, ' '))
         << "Hash value = " << std::hex << '(';
      internal::print_tuple(val, os, std::make_index_sequence<std::tuple_size_v<decltype(val)>> {});
      os << ")\n";
      os.flags(prev_state);
    }
  };

public:
  template <typename Container>
  rolling_hash(const Container& source)
      : src(std::cbegin(source), std::cend(source)), hashes(internal::build_hash_sequence<Bases...>(src)) {}

  [[nodiscard]] int size() const noexcept(noexcept(std::size(src))) {
    return static_cast<int>(std::size(src));
  }

  [[nodiscard]] single_hash whole_string() const {
    return single_hash(src, hashes.back(), size());
  }

  [[nodiscard]] single_hash substring(const int starts, int length = std::numeric_limits<int>::max()) const {
    length = std::min(static_cast<int>(std::size(src)) - starts, length);
    return single_hash(std::vector<Elem>(std::cbegin(src) + starts, std::cbegin(src) + starts + length), internal::substr_hash<Bases...>(hashes, starts, length), length);
  }
};
#  else
template <typename Elem, std::uint32_t... Bases>
class rolling_hash {
private:
  std::vector<decltype(std::tuple {(static_cast<internal::u64>(Bases))...})> hashes;

  struct single_hash {
  private:
    decltype(std::tuple {(static_cast<internal::u64>(Bases))...}) val;
    int length;

  public:
    constexpr single_hash() noexcept
        : val(), length() {}
    constexpr single_hash(const decltype(std::tuple {(static_cast<internal::u64>(Bases))...})& hash, const int size)
        : val(hash), length(size) {}
    constexpr single_hash(decltype(std::tuple {(static_cast<internal::u64>(Bases))...})&& hash, const int size)
        : val(std::move(hash)), length(size) {}

    [[nodiscard]] constexpr int size() const noexcept {
      return length;
    }

    [[nodiscard]] constexpr bool operator==(const single_hash& rhs) const noexcept {
      return (length == rhs.length) && (val == rhs.val);
    }

    [[nodiscard]] constexpr bool operator!=(const single_hash& rhs) const noexcept {
      return !(*this == rhs);
    }

    [[nodiscard]] constexpr auto hash_value() const noexcept {
      return val;
    }

    void debug_print([[maybe_unused]] const std::string& name = "", [[maybe_unused]] std::ostream& os = std::cerr) const {
#    if (CP_LIBRARY_DEBUG_LEVEL >= 1)
      if (!name.empty())
        os << name << ": ";

      const std::ios_base::fmtflags prev_state = os.flags();
      os << "Hash value = " << std::hex << '(';
      internal::print_tuple(val, os, std::make_index_sequence<std::tuple_size_v<decltype(val)>> {});
      os << ")\n";
      os.flags(prev_state);
#    endif
    }
  };

public:
  template <typename Container>
  rolling_hash(const Container& source)
      : hashes(internal::build_hash_sequence<Bases...>(source)) {}

  [[nodiscard]] int size() const noexcept(noexcept(std::size(hashes))) {
    return static_cast<int>(std::size(hashes)) - 1;
  }

  [[nodiscard]] single_hash whole_string() const {
    return single_hash(hashes.back(), size());
  }

  [[nodiscard]] single_hash substring(const int starts, int length = std::numeric_limits<int>::max()) const {
    length = std::min(static_cast<int>(std::size(hashes)) - starts - 1, length);
    return single_hash(internal::substr_hash<Bases...>(hashes, starts, length), length);
  }
};
#  endif

template <typename Container>
[[nodiscard]] auto get_rolling_hash(const Container& src) {
  return rolling_hash<std::decay_t<decltype(*std::cbegin(std::declval<Container>()))>, 436523069, 681531337, 843203861>(src);
}

template <typename Container>
[[nodiscard]] auto get_single_hash(const Container& src) {
  return get_rolling_hash(src).whole_string();
}

template <typename Container>
using rolling_hash_t = decltype(get_rolling_hash(std::declval<Container>()));
template <typename Container>
using single_hash_t = decltype(get_single_hash(std::declval<Container>()));

}  // namespace lib

#  ifdef err_and_exit_not_defined
#    undef err_and_exit
#    undef err_and_exit_not_defined
#  endif

#  ifdef O_assert_not_defined
#    undef O_assert
#    undef O_assert_not_defined
#  endif

#  ifdef ROLLING_HASH_MAX_LENGTH_not_defined
#    undef ROLLING_HASH_MAX_LENGTH
#    undef ROLLING_HASH_MAX_LENGTH_not_defined
#  endif

#endif  // ROLLING_HASH_HPP

#include <iostream>
#include <string>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::string S;
  std::cin >> S;

  const auto S_hashes = lib::get_rolling_hash(S);
  const auto S_len    = static_cast<int>(std::size(S));

  std::vector precalc_hashes(S_len, std::vector<lib::single_hash_t<std::string>>(11));

  for (int len = 1; len <= 10; ++len)
    for (int start = 0; start <= S_len - len; ++start)
      precalc_hashes[start][len] = S_hashes.substring(start, len);

  int M, res = 0;
  std::cin >> M;

  std::string tmp;

  while (M--) {
    std::cin >> tmp;
    const auto tmp_hash = lib::get_single_hash(tmp);
    const auto tmp_len  = static_cast<int>(std::size(tmp));

    std::cerr << tmp << '\n';

    for (int start = 0; start <= S_len - tmp_len; ++start)
      res += static_cast<int>(precalc_hashes[start][tmp_len] == tmp_hash);
  }

  std::cout << res << '\n';
}
yukicoder

結果

テストケース

ソースコード
