結果

問題 No.765 ukuku 2
ユーザー ei1333333ei1333333
提出日時 2018-10-30 01:57:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 253 ms / 3,000 ms
コード長 5,244 bytes
コンパイル時間 2,553 ms
コンパイル使用メモリ 215,900 KB
実行使用メモリ 50,840 KB
最終ジャッジ日時 2023-08-26 19:58:21
合計ジャッジ時間 8,795 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,384 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 196 ms
48,972 KB
testcase_31 AC 204 ms
48,636 KB
testcase_32 AC 126 ms
27,056 KB
testcase_33 AC 123 ms
50,712 KB
testcase_34 AC 123 ms
50,820 KB
testcase_35 AC 236 ms
50,772 KB
testcase_36 AC 253 ms
50,784 KB
testcase_37 AC 121 ms
50,724 KB
testcase_38 AC 138 ms
50,780 KB
testcase_39 AC 176 ms
50,840 KB
testcase_40 AC 167 ms
49,036 KB
testcase_41 AC 184 ms
49,640 KB
testcase_42 AC 201 ms
49,904 KB
testcase_43 AC 182 ms
49,120 KB
testcase_44 AC 184 ms
49,176 KB
testcase_45 AC 206 ms
49,952 KB
testcase_46 AC 186 ms
49,152 KB
testcase_47 AC 218 ms
50,500 KB
testcase_48 AC 237 ms
50,144 KB
testcase_49 AC 225 ms
50,044 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
using pi = pair< int, int >;

struct SuffixArray {
  vector< int > SA;
  const string s;

  SuffixArray(const string &str) : s(str) {
    SA.resize(s.size());
    iota(begin(SA), end(SA), 0);
    sort(begin(SA), end(SA), [&](int a, int b) {
      return s[a] == s[b] ? a > b : s[a] < s[b];
    });
    vector< int > classes(s.size()), c(s.begin(), s.end()), cnt(s.size());
    for(int len = 1; len < s.size(); len <<= 1) {
      for(int i = 0; i < s.size(); i++) {
        if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(begin(cnt), end(cnt), 0);
      copy(begin(SA), end(SA), begin(c));
      for(int i = 0; i < s.size(); i++) {
        int s1 = c[i] - len;
        if(s1 >= 0) SA[cnt[classes[s1]]++] = s1;
      }
      classes.swap(c);
    }
  }

  int operator[](int k) const {
    return SA[k];
  }

  size_t size() const {
    return s.size();
  }

  bool lt_substr(const string &t, int si = 0, int ti = 0) {
    int sn = (int) s.size(), tn = (int) t.size();
    while(si < sn && ti < tn) {
      if(s[si] < t[ti]) return true;
      if(s[si] > t[ti]) return false;
      ++si, ++ti;
    }
    return si >= sn && ti < tn;
  }

  int lower_bound(const string &t) {
    int low = -1, high = (int) SA.size();
    while(high - low > 1) {
      int mid = (low + high) / 2;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    return high;
  }

  pair< int, int > lower_upper_bound(string &t) {
    int idx = lower_bound(t);
    int low = idx - 1, high = (int) SA.size();
    t.back()++;
    while(high - low > 1) {
      int mid = (low + high) / 2;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    t.back()--;
    return {idx, high};
  }

  void output() {
    for(int i = 0; i < size(); i++) {
      cout << i << ": " << s.substr(SA[i]) << endl;
    }
  }
};

struct LongestCommonPrefixArray {
  const SuffixArray &SA;
  vector< int > LCP, rank;

  LongestCommonPrefixArray(const SuffixArray &SA) : SA(SA), LCP(SA.size()) {
    rank.resize(SA.size());
    for(int i = 0; i < SA.size(); i++) {
      rank[SA[i]] = i;
    }
    for(int i = 0, h = 0; i < SA.size(); i++) {
      if(rank[i] + 1 < SA.size()) {
        for(int j = SA[rank[i] + 1]; max(i, j) + h < SA.size() && SA.s[i + h] == SA.s[j + h]; ++h);
        LCP[rank[i] + 1] = h;
        if(h > 0) --h;
      }
    }
  }

  int operator[](int k) const {
    return LCP[k];
  }

  size_t size() const {
    return LCP.size();
  }

  void output() {
    for(int i = 0; i < size(); i++) {
      cout << i << ": " << LCP[i] << " " << SA.s.substr(SA[i]) << endl;
    }
  }
};

template< typename T >
struct SparseTable {
  vector< vector< T > > st;
  vector< int > lookup;

  SparseTable(const vector< T > &v) {
    int b = 0;
    while((1 << b) <= v.size()) ++b;
    st.assign(b, vector< T >(1 << b));
    for(int i = 0; i < v.size(); i++) {
      st[0][i] = v[i];
    }
    for(int i = 1; i < b; i++) {
      for(int j = 0; j + (1 << i) <= (1 << b); j++) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(v.size() + 1);
    for(int i = 2; i < lookup.size(); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  inline T rmq(int l, int r) {
    int b = lookup[r - l];
    return min(st[b][l], st[b][r - (1 << b)]);
  }
};

const int INF = 1 << 30;


int main() {
  string S;
  cin >> S;
  assert(2 <= S.size() && S.size() <= 200000);
  for(auto &c : S) assert(islower(c));
  string T = S;
  reverse(begin(T), end(T));
  T = S + "$" + T;
  SuffixArray sa(T);
  LongestCommonPrefixArray lcp(sa);
  SparseTable< int > table(lcp.LCP);
  vector< int > latte(S.size()), malta(S.size());

  for(int i = 0; i < T.size(); i++) {
    int pos = sa[i];
    if(pos == S.size()) continue;
    if(pos > S.size()) {
      pos -= S.size() + 1;
      pos = (int) S.size() - pos - 1;
      malta[pos] = i;
    } else {
      latte[pos] = i;
    }
  }
  auto get_lcp = [&](int x, int y) {
    if(x > y) swap(x, y);
    return table.rmq(x + 1, y + 1);
  };
  int ret = 0;
  for(int i = 0; i < S.size(); i++) {
    auto lcp = get_lcp(latte[i], malta[i]);
    if(i - lcp >= 0) {
      auto add = lcp;
      if(i - lcp - 1 >= 0 && i + lcp < S.size()) add += get_lcp(latte[i + lcp], malta[i - lcp - 1]);
      ret = max(ret, add * 2 - 1);
    }
    if(i + lcp < S.size()) {
      auto add = lcp;
      if(i - lcp >= 0 && i + lcp + 1 < S.size()) add += get_lcp(latte[i + lcp + 1], malta[i - lcp]);
      ret = max(ret, add * 2 - 1);
    }
  }
  for(int i = 1; i < S.size(); i++) {
    auto lcp = get_lcp(latte[i], malta[i - 1]);
    if(i - lcp - 1 >= 0) {
      auto add = lcp;
      if(i - lcp - 2 >= 0 && i + lcp < S.size()) add += get_lcp(latte[i + lcp], malta[i - lcp - 2]);
      ret = max(ret, add * 2);
    }
    if(i + lcp < S.size()) {
      auto add = lcp;
      if(i - lcp - 1 >= 0 && i + lcp + 1 < S.size()) add += get_lcp(latte[i + lcp + 1], malta[i - lcp - 1]);
      ret = max(ret, add * 2);
    }
  }
  cout << ret << endl;
}
0