結果
| 問題 | No.765 ukuku 2 |
| ユーザー |
 hirokazu1020
|
| 提出日時 | 2018-12-16 04:44:01 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 116 ms / 3,000 ms |
| コード長 | 8,095 bytes |
| コンパイル時間 | 1,153 ms |
| コンパイル使用メモリ | 115,024 KB |
| 実行使用メモリ | 42,556 KB |
| 最終ジャッジ日時 | 2024-09-25 06:26:06 |
| 合計ジャッジ時間 | 4,180 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 48 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<sstream>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<cmath>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<numeric>#include<functional>#include<algorithm>#include<bitset>#include<tuple>#include<unordered_set>#include<unordered_map>#include<random>#include<array>#include<cassert>using namespace std;#define INF (1<<29)#define rep(i,n) for(int i=0;i<(int)(n);i++)#define all(v) v.begin(),v.end()#define uniq(v) v.erase(unique(all(v)),v.end())class SuffixArray {string text;vector<int> sa;static bool eq(const vector<int> &v, int idx1, int idx2, const vector<bool> &type) {if (v[idx1] != v[idx2])return false;int last = v.size() - 1;for (int i = 1;; i++) {if (v[idx1 + i] != v[idx2 + i])return false;if (idx1 + i == last || type[idx1 + i - 1] && !type[idx1 + i])return idx2 + i == last || type[idx2 + i - 1] && !type[idx2 + i];else if (idx2 + i == last || type[idx2 + i - 1] && !type[idx2 + i])return false;}return true;}template<bool erase>static inline void Lsort(const vector<int> &v, const vector<bool> &type, vector<int> &bucket, vector<int> &rank_less) {for (int i = 0; i < (int)bucket.size(); i++) {if (bucket[i] > 0 && type[bucket[i] - 1]) {bucket[rank_less[v[bucket[i] - 1]]++] = bucket[i] - 1;if (erase)bucket[i] = -1;}}}template<bool erase>static inline void Ssort(const vector<int> &v, const vector<bool> &type, vector<int> &bucket, vector<int> &rank_less_eq) {for (int i = bucket.size() - 1; i >= 0; i--) {if (bucket[i] > 0 && !type[bucket[i] - 1]) {bucket[--rank_less_eq[v[bucket[i] - 1]]] = bucket[i] - 1;if (erase)bucket[i] = -1;}}}static vector<int> induced_sorting(const vector<int> &v, int alpha) {vector<int> bucket(v.size());vector<int> rank(alpha), c(alpha);vector<bool> type(v.size());//false=>S,true=>Lvector<int> lmsidx, lmsord;type.back() = true;for (int i = v.size() - 2; i >= 0; i--) {if (v[i] < v[i + 1])type[i] = false;else if (v[i] > v[i + 1])type[i] = true;else type[i] = type[i + 1];}for (int i = 0; i < (int)v.size(); i++)rank[v[i]]++;for (int i = 1; i < alpha; i++)rank[i] += rank[i - 1];//sorting LMS-substringfill(bucket.begin(), bucket.end(), -1);bool first = true;copy(rank.begin(), rank.end(), c.begin());for (int i = 1; i < (int)v.size(); i++) {if (type[i - 1] && !type[i]) {//LMSif (first)first = false;else bucket[--c[v[i]]] = i;}}copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1);c[0] = 0;bucket[c[v.back()]++] = v.size() - 1;Lsort<true>(v, type, bucket, c);copy(rank.begin(), rank.end(), c.begin());Ssort<true>(v, type, bucket, c);for (int i = 0; i < (int)bucket.size(); i++)if (bucket[i] > 0)lmsidx.push_back(bucket[i]);if (!lmsidx.empty()) {lmsord.resize(lmsidx.size());lmsord[0] = 0;for (int i = 1; i < (int)lmsidx.size(); i++) {if (eq(v, lmsidx[i - 1], lmsidx[i], type))lmsord[i] = lmsord[i - 1];else lmsord[i] = lmsord[i - 1] + 1;}if (lmsord.back() + 1 != lmsord.size()) {vector<int> lmssuffix;fill(bucket.begin(), bucket.end(), -1);for (int i = 0; i < (int)lmsidx.size(); i++) {if (lmsidx[i])bucket[lmsidx[i]] = lmsord[i];}lmsidx.clear();for (int i = 0; i < (int)bucket.size(); i++) {if (bucket[i] != -1) {lmssuffix.push_back(bucket[i]);lmsidx.push_back(i);}}vector<int> lmssa(induced_sorting(lmssuffix, lmsord.back() + 1));for (int i = 0; i < (int)lmsidx.size(); i++) {lmsord[i] = lmsidx[lmssa[i]];}lmsidx.swap(lmsord);}lmsord.clear();}//ended sorting LMS-substringfill(bucket.begin(), bucket.end(), -1);copy(rank.begin(), rank.end(), c.begin());for (int i = lmsidx.size() - 1; i >= 0; i--)bucket[--c[v[lmsidx[i]]]] = lmsidx[i];copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1);c[0] = 0;bucket[c[v.back()]++] = v.size() - 1;Lsort<false>(v, type, bucket, c);copy(rank.begin(), rank.end(), c.begin());Ssort<false>(v, type, bucket, c);return bucket;}public:SuffixArray(const string &s) {build(s);}const string& get_text()const { return text; }void build(const string &s) {text = s;vector<int> v(s.size());for (int i = 0; i < (int)s.size(); i++)v[i] = s[i] - 'a';sa = induced_sorting(v, 27);}bool contain(const string &s)const {int a = -1, b = text.size() - 1;while (b - a > 1) {int c = (a + b) / 2;if (text.compare(sa[c], s.size(), s) < 0)a = c;else b = c;}return text.compare(sa[b], s.size(), s) == 0;}int lower_bound(string &s)const {int a = -1, b = text.size();while (b - a > 1) {int c = (a + b) / 2;if (text.compare(sa[c], s.size(), s) < 0)a = c;else b = c;}return b;}int upper_bound(string &s)const {int a = -1, b = text.size();while (b - a > 1) {int c = (a + b) / 2;if (text.compare(sa[c], s.size(), s) <= 0)a = c;else b = c;}return b;}string nth_suffix(int k)const {return text.substr(sa[k]);}int ord(int i)const {return sa[i];}vector<int> construct_lcp()const {//高さ配列を返すint n = text.size();int h = 0;vector<int> lcp(n - 1), rank(n);for (int i = 0; i < n; i++) rank[sa[i]] = i;lcp[0] = 0;for (int i = 0; i < n; i++) {if (rank[i] == 0)continue;int j = sa[rank[i] - 1];if (h > 0)h--;for (; j + h < n&&i + h < n; h++)if (text[j + h] != text[i + h])break;lcp[rank[i] - 1] = h;}return lcp;}};class SparseTableRMQ {int maxlog;std::vector<char> log;std::vector<int> M;public:SparseTableRMQ(const std::vector<int> &a) {int n = a.size();log.resize(n + 1);log[0] = 0;for (int i = 1, a = 0; i <= n; i++) {if ((1 << a + 1) < i)a++;log[i] = a;}maxlog = log[n] + 1;M.resize(n*maxlog);for (int i = 0; i < n; i++)M[i*maxlog] = a[i];for (int j = 1; 1 << j <= n; j++) {for (int i = 0; i + (1 << j) - 1 < n; i++) {M[i*maxlog + j] = std::min(M[i*maxlog + j - 1], M[(i + (1 << j - 1))*maxlog + j - 1]);}}}int query(int i, int j)const {//[i,j)の最小値int k = log[j - i];return std::min(M[i*maxlog + k], M[(j - (1 << k))*maxlog + k]);}};int main() {ios::sync_with_stdio(0);cin.tie(0);string s;cin >> s;int n = s.size();string ss;ss += s;reverse(all(s));ss += 'z' + 1;ss += s;SuffixArray sa(ss);vector<int> ord(2 * n + 1);rep(i, 2 * n + 1)ord[sa.ord(i)] = i;vector<int> lcp = sa.construct_lcp();SparseTableRMQ rmq(lcp);int ans = 0;for (int i = 0; i < n; i++) {int a = min(ord[i], ord[2 * n - i]);int b = max(ord[i], ord[2 * n - i]);int c = rmq.query(a, b);if (2 * c - 1 == n)ans = max(ans, 2 * c - 1 - 2);else ans = max(ans, 2 * c - 1);if (0 <= i - c - 1 && i + c < n) {int x = min(ord[i + c], ord[2 * n - (i - c - 1)]);int y = max(ord[i + c], ord[2 * n - (i - c - 1)]);int z = rmq.query(x, y);ans = max(ans, 2 * (c + z) - 1);}if (0 <= i - c && i + c + 1 < n) {int x = min(ord[i + c + 1], ord[2 * n - (i - c)]);int y = max(ord[i + c + 1], ord[2 * n - (i - c)]);int z = rmq.query(x, y);ans = max(ans, 2 * (c + z) - 1);}}for (int i = 0; i + 1 < n; i++) {int a = min(ord[i + 1], ord[2 * n - (i)]);int b = max(ord[i + 1], ord[2 * n - (i)]);int c = rmq.query(a, b);if (2 * c == n)ans = max(ans, 2 * c - 2);else ans = max(ans, 2 * c);if (0 <= i - c - 1 && i + 1 + c < n) {int x = min(ord[i + 1 + c], ord[2 * n - (i - c - 1)]);int y = max(ord[i + 1 + c], ord[2 * n - (i - c - 1)]);int z = rmq.query(x, y);ans = max(ans, 2 * (c + z));}if (0 <= i - c && i + 1 + c + 1 < n) {int x = min(ord[i + 1 + c + 1], ord[2 * n - (i - c)]);int y = max(ord[i + 1 + c + 1], ord[2 * n - (i - c)]);int z = rmq.query(x, y);ans = max(ans, 2 * (c + z));}}cout << ans << endl;return 0;}