結果

問題 No.273 回文分解
ユーザー koyumeishi
提出日時 2015-08-28 22:31:15
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 4 ms
コード長 1,679 Byte
コンパイル時間 528 ms
使用メモリ 3,488 KB
最終ジャッジ日時 2020-01-17 08:44:41

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 4 ms
3,252 KB
99_system_test2.txt AC 4 ms
3,356 KB
99_system_test3.txt AC 0 ms
3,348 KB
sample1.txt AC 0 ms
3,384 KB
sample2.txt AC 0 ms
3,328 KB
sample3.txt AC 4 ms
3,484 KB
system_test1.txt AC 4 ms
3,296 KB
system_test2.txt AC 0 ms
3,396 KB
system_test3.txt AC 0 ms
3,340 KB
system_test4.txt AC 4 ms
3,392 KB
system_test5.txt AC 4 ms
3,328 KB
system_test6.txt AC 0 ms
3,344 KB
system_test7.txt AC 0 ms
3,392 KB
system_test8.txt AC 4 ms
3,340 KB
system_test9.txt AC 4 ms
3,488 KB
test1.txt AC 0 ms
3,480 KB
test2.txt AC 0 ms
3,460 KB
test3.txt AC 0 ms
3,348 KB
test4.txt AC 4 ms
3,276 KB
test5.txt AC 4 ms
3,296 KB
test6.txt AC 0 ms
3,344 KB
test7.txt AC 0 ms
3,400 KB
test8.txt AC 4 ms
3,316 KB
test9.txt AC 0 ms
3,296 KB
test10.txt AC 0 ms
3,392 KB
test11.txt AC 4 ms
3,348 KB
test12.txt AC 4 ms
3,320 KB
test13.txt AC 0 ms
3,260 KB
test14.txt AC 0 ms
3,320 KB
test15.txt AC 0 ms
3,464 KB
test16.txt AC 0 ms
3,352 KB
test17.txt AC 4 ms
3,316 KB
test18.txt AC 4 ms
3,328 KB
test19.txt AC 4 ms
3,272 KB
test20.txt AC 0 ms
3,388 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