結果

問題 No.765 ukuku 2
ユーザー hirokazu1020hirokazu1020
提出日時 2018-12-16 04:44:01
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 1 ms
6,948 KB
testcase_28 AC 1 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 96 ms
32,500 KB
testcase_31 AC 95 ms
30,744 KB
testcase_32 AC 69 ms
26,396 KB
testcase_33 AC 64 ms
40,052 KB
testcase_34 AC 68 ms
40,140 KB
testcase_35 AC 114 ms
42,556 KB
testcase_36 AC 109 ms
42,532 KB
testcase_37 AC 76 ms
40,652 KB
testcase_38 AC 97 ms
40,572 KB
testcase_39 AC 102 ms
40,232 KB
testcase_40 AC 85 ms
33,268 KB
testcase_41 AC 89 ms
36,204 KB
testcase_42 AC 97 ms
37,608 KB
testcase_43 AC 84 ms
33,328 KB
testcase_44 AC 85 ms
34,476 KB
testcase_45 AC 100 ms
38,144 KB
testcase_46 AC 86 ms
32,832 KB
testcase_47 AC 116 ms
38,000 KB
testcase_48 AC 106 ms
37,256 KB
testcase_49 AC 116 ms
37,364 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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=>L
		vector<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-substring
		fill(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]) {//LMS
				if (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-substring
		fill(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;
}
0