Submission #7564275


Source Code Expand

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

Submission Info

Submission Time
Task E - Who Says a Pun?
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2111 Byte
Status
Exec Time 24 ms
Memory 896 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-00, 00-sample-01, 00-sample-02
All 500 / 500 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 01-handmade-12, 02-binary-13, 02-binary-14, 02-binary-15, 02-binary-16, 02-binary-17, 02-binary-18, 02-binary-19, 02-binary-20, 02-binary-21, 02-binary-22, 02-binary-23, 03-BigRandom-24, 03-BigRandom-25, 03-BigRandom-26, 03-BigRandom-27, 03-BigRandom-28, 03-BigRandom-29, 03-BigRandom-30, 03-BigRandom-31, 03-BigRandom-32, 03-BigRandom-33, 03-BigRandom-34, 03-BigRandom-35, 03-BigRandom-36, 03-BigRandom-37, 03-BigRandom-38, 03-BigRandom-39, 03-BigRandom-40, 03-BigRandom-41, 03-BigRandom-42, 03-BigRandom-43, 03-BigRandom-44, 03-BigRandom-45, 03-BigRandom-46, 03-BigRandom-47, 03-BigRandom-48, 03-BigRandom-49, 03-BigRandom-50, 03-BigRandom-51, 03-BigRandom-52, 03-BigRandom-53, 03-BigRandom-54, 04-zero-55, 04-zero-56, 05-AllRandom-57, 05-AllRandom-58, 05-AllRandom-59, 05-AllRandom-60, 05-AllRandom-61, 05-AllRandom-62, 05-AllRandom-63, 05-AllRandom-64, 05-AllRandom-65, 05-AllRandom-66, 05-AllRandom-67, 05-AllRandom-68, 05-AllRandom-69
Case Name Status Exec Time Memory
00-sample-00 1 ms 256 KB
00-sample-01 1 ms 256 KB
00-sample-02 1 ms 256 KB
01-handmade-03 4 ms 384 KB
01-handmade-04 17 ms 768 KB
01-handmade-05 14 ms 640 KB
01-handmade-06 14 ms 640 KB
01-handmade-07 14 ms 640 KB
01-handmade-08 4 ms 384 KB
01-handmade-09 19 ms 896 KB
01-handmade-10 19 ms 896 KB
01-handmade-11 7 ms 640 KB
01-handmade-12 10 ms 640 KB
02-binary-13 20 ms 768 KB
02-binary-14 21 ms 896 KB
02-binary-15 17 ms 768 KB
02-binary-16 21 ms 896 KB
02-binary-17 22 ms 896 KB
02-binary-18 18 ms 896 KB
02-binary-19 15 ms 768 KB
02-binary-20 16 ms 768 KB
02-binary-21 16 ms 768 KB
02-binary-22 14 ms 768 KB
02-binary-23 14 ms 768 KB
03-BigRandom-24 12 ms 640 KB
03-BigRandom-25 12 ms 640 KB
03-BigRandom-26 14 ms 640 KB
03-BigRandom-27 16 ms 768 KB
03-BigRandom-28 17 ms 768 KB
03-BigRandom-29 15 ms 768 KB
03-BigRandom-30 18 ms 768 KB
03-BigRandom-31 14 ms 640 KB
03-BigRandom-32 18 ms 768 KB
03-BigRandom-33 17 ms 768 KB
03-BigRandom-34 14 ms 640 KB
03-BigRandom-35 15 ms 768 KB
03-BigRandom-36 16 ms 768 KB
03-BigRandom-37 12 ms 640 KB
03-BigRandom-38 13 ms 640 KB
03-BigRandom-39 13 ms 640 KB
03-BigRandom-40 14 ms 768 KB
03-BigRandom-41 14 ms 640 KB
03-BigRandom-42 14 ms 640 KB
03-BigRandom-43 12 ms 640 KB
03-BigRandom-44 14 ms 640 KB
03-BigRandom-45 15 ms 768 KB
03-BigRandom-46 14 ms 640 KB
03-BigRandom-47 17 ms 768 KB
03-BigRandom-48 13 ms 640 KB
03-BigRandom-49 14 ms 768 KB
03-BigRandom-50 15 ms 768 KB
03-BigRandom-51 13 ms 640 KB
03-BigRandom-52 14 ms 768 KB
03-BigRandom-53 14 ms 768 KB
03-BigRandom-54 14 ms 640 KB
04-zero-55 1 ms 256 KB
04-zero-56 1 ms 256 KB
05-AllRandom-57 24 ms 896 KB
05-AllRandom-58 23 ms 896 KB
05-AllRandom-59 22 ms 896 KB
05-AllRandom-60 23 ms 896 KB
05-AllRandom-61 21 ms 896 KB
05-AllRandom-62 23 ms 896 KB
05-AllRandom-63 23 ms 896 KB
05-AllRandom-64 21 ms 896 KB
05-AllRandom-65 23 ms 896 KB
05-AllRandom-66 21 ms 896 KB
05-AllRandom-67 22 ms 896 KB
05-AllRandom-68 24 ms 896 KB
05-AllRandom-69 24 ms 896 KB