結果

問題 No.273 回文分解
ユーザー koyumeishikoyumeishi
提出日時 2015-08-28 22:31:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,679 bytes
コンパイル時間 704 ms
コンパイル使用メモリ 81,872 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-07 19:38:19
合計ジャッジ時間 2,065 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,384 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,384 KB
testcase_21 AC 2 ms
4,384 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 2 ms
4,380 KB
testcase_33 AC 2 ms
4,376 KB
testcase_34 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;


//palindrome
class Manacher{
	string s;
	int n;
	vector<int> radius;
	
public:
	Manacher(string &s_){
		n = s_.size();
		s = string(2*n+1, '#');
		for(int i=0; i<n; i++){
			s[2*i + 1] = s_[i];
		}
		n = s.size();

		radius = vector<int>(n, -1);
		for(int i=0, j=0; i<n; ){
			while(1){
				if(i-j < 0 || i+j >= n) break;

				if(s[i-j] == s[i+j]) j++;
				else break;
			}
			radius[i] = j;

			int k = 1;
			while(1){
				if(i-k < 0 || i+k >= n) break;

				if(radius[i-k] < radius[i] - k){
					radius[i+k] = radius[i-k];
					k++;
				}else break;
			}

			i += k;
			j = max(j-k, 0);
		}
	}

	int get_longest_palindrome(){
		return (int)*max_element(radius.begin(), radius.end());
	}

	int count_palindromes(){
		int MOD = 1000000007;
		vector<long long> sum(n+10, 0);
		for(int i=0; i<n; i++){
			int len;
			if(i%2==0){
				len = (radius[i]/2) * 2;
			}else{
				len = ((radius[i]-1)/2) * 2 + 1;
			}
			sum[(len%2==0)?2:1] += 1;
			sum[len+2] -= 1;
		}

		long long ret = 0;
		vector<long long> tmp(2, 0);
		for(int i=1; i<=n; i++){
			tmp[i&1] += sum[i];
			tmp[i&1] %= MOD;
			ret += tmp[i&1] * i;
			ret %= MOD;
		}
		return ret;
	}
};


int main(){
	string s;
	cin >> s;

	int ans = 1;
	int n = s.size();
	for(int i=1; i<n; i++){
		string a = s.substr(0, i);
		string b = s.substr(i, n-i);


		Manacher x(a), y(b);
		vector<int> v = {x.get_longest_palindrome()-1, y.get_longest_palindrome()-1};
		ans = max({ans, v[0], v[1]});

	}
	cout << ans << endl;

	return 0;
}
0