文字列/rolling hash
(test/string/rolling_hash.test.cpp)

• View this file on GitHub
• Last update: 2023-07-21 12:14:05+09:00
• Problem: https://atcoder.jp/contests/abc141/tasks/abc141_e

Depends on

• rolling hash (include/emthrm/string/rolling_hash.hpp)

Code

/*
 * @title 文字列/rolling hash
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/abc141/tasks/abc141_e
 */

#include <iostream>
#include <set>
#include <string>

#include "emthrm/string/rolling_hash.hpp"

int main() {
  int n;
  std::string s;
  std::cin >> n >> s;
  emthrm::RollingHash<> rolling_hash(s);
  for (int len = n - 1; len >= 1; --len) {
    std::set<std::int64_t> hashes;
    for (int i = len; i + len <= n; ++i) {
      hashes.emplace(rolling_hash.get(i - len, i));
      if (hashes.contains(rolling_hash.get(i, i + len))) {
        std::cout << len << '\n';
        return 0;
      }
    }
  }
  std::cout << 0 << '\n';
  return 0;
}

#line 1 "test/string/rolling_hash.test.cpp"
/*
 * @title 文字列/rolling hash
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/abc141/tasks/abc141_e
 */

#include <iostream>
#include <set>
#include <string>

#line 1 "include/emthrm/string/rolling_hash.hpp"



#include <cassert>
#include <cstdint>
#include <random>
#include <vector>

namespace emthrm {

template <typename T = char>
struct RollingHash {
  const std::int64_t base;
  std::vector<T> str;

  template <typename U>
  explicit RollingHash(const U& str_, const std::int64_t base = generate_base())
      : base(base), hashes({0}), powers({1}) {
    const int n = str_.size();
    str.reserve(n);
    hashes.reserve(n + 1);
    powers.reserve(n + 1);
    for (const auto ch : str_) add(ch);
  }

  void add(const T ch) {
    assert(0 <= ch && ch < MOD);
    str.emplace_back(ch);
    const std::int64_t h = mul(hashes.back(), base) + ch;
    hashes.emplace_back(h >= MOD ? h - MOD : h);
    const std::int64_t p = mul(powers.back(), base);
    powers.emplace_back(p);
  }

  std::int64_t get(const int left, const int right) const {
    const std::int64_t res =
        hashes[right] - mul(hashes[left], powers[right - left]);
    return res < 0 ? res + MOD : res;
  }

 private:
  static constexpr int MOD_WIDTH = 61;
  static constexpr std::int64_t MOD = (INT64_C(1) << MOD_WIDTH) - 1;

  std::vector<std::int64_t> hashes, powers;

  static std::int64_t generate_base() {
    static std::mt19937_64 engine(std::random_device {} ());
    static std::uniform_int_distribution<std::int64_t> dist(0, MOD - 1);
    return dist(engine);
  }

  static std::int64_t mul(const std::int64_t a, const std::int64_t b) {
    const std::int64_t au = a >> 31, ad = a & ((UINT32_C(1) << 31) - 1);
    const std::int32_t bu = b >> 31, bd = b & ((UINT32_C(1) << 31) - 1);
    const std::int64_t mid = au * bd + ad * bu;
    std::int64_t res = au * bu * 2 + ad * bd + (mid >> 30)
                       + ((mid & ((UINT32_C(1) << 30) - 1)) << 31);
    res = (res >> MOD_WIDTH) + (res & MOD);
    return res >= MOD ? res - MOD : res;
  }
};

}  // namespace emthrm


#line 13 "test/string/rolling_hash.test.cpp"

int main() {
  int n;
  std::string s;
  std::cin >> n >> s;
  emthrm::RollingHash<> rolling_hash(s);
  for (int len = n - 1; len >= 1; --len) {
    std::set<std::int64_t> hashes;
    for (int i = len; i + len <= n; ++i) {
      hashes.emplace(rolling_hash.get(i - len, i));
      if (hashes.contains(rolling_hash.get(i, i + len))) {
        std::cout << len << '\n';
        return 0;
      }
    }
  }
  std::cout << 0 << '\n';
  return 0;
}

Back to top page