提出 #7564275

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

class RollingHash {
 public:
  explicit RollingHash(const std::string &s) {
    mod = std::vector<ll>{999999937LL, 1000000007LL};
    base = 9973;
    n = s.size();
    for (int i = 0; i < MS; i++) {
      hs[i].assign(n+1, 0);
      pw[i].assign(n+1, 0);
      hs[i][0] = 0;
      pw[i][0] = 1;
      for (int j = 0; j < n; j++) {
        pw[i][j+1] = pw[i][j]*base%mod[i];
        hs[i][j+1] = (hs[i][j]*base+s[j])%mod[i];
      }
    }
  }
  bool match(int l1, int r1, int l2, int r2) {
    bool ret = 1;
    for (int i = 0; i < MS; i++)
      ret &= hash(l1, r1, i) == hash(l2, r2, i);
    return ret;
  }

  std::vector<ll> get_hash(int l, int r) {
    std::vector <ll> res(MS);
    for (int i = 0; i < MS; i++)
      res[i] = hash(l, r, i);
    return res;
  }

 private:
  static const int MAX = 500000, MS = 2;
  std::vector<ll> mod;
  ll base;
  int n;
  std::vector<ll> hs[MS], pw[MS];
  ll hash(int l, int r, int i) {
    return ((hs[i][r]-hs[i][l]*pw[i][r-l])%mod[i]+mod[i])%mod[i];
  }

  bool match(int l, int r, ll h[]) {
    bool ret = 1;
    for (int i = 0; i < MS; i++)
      ret &= hash(l, r, i) == h[i];
    return ret;
  }
};

signed main() {
  ll N;
  string s;
  cin >> N >> s;
  RollingHash rh(s);
  ll ng = 2501, ok = 0;
  while (ok + 1 < ng) {
    ll m = (ok+ng)/2;
    // cout << m << endl;
    bool t = false;

    map<vector<ll>, ll> mp; // mp[hash value] = index
    rep(i,N) {
      if (i+m > N)
        continue;

      auto h = rh.get_hash(i, i+m);
      auto it = mp.find(h);
      if (it == mp.end()) {
        mp[h] = i;
      } else {
        // hash find
        if (it->second + m <= i) {
          t = true;
          break;
        }
      }
    }

    if (t) {
      ok = m;
    } else {
      ng = m;
    }
  }

  cout << ok << endl;
  return 0;
}

提出情報

ジャッジ結果