結果

問題 No.273 回文分解
ユーザー koyumeishi
提出日時 2015-08-28 22:31:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,679 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 80,360 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-25 13:24:18
合計ジャッジ時間 1,745 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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