結果

問題 No.273 回文分解
ユーザー tubo28
提出日時 2015-08-28 22:23:46
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 4 ms
コード長 2,189 Byte
コンパイル時間 936 ms
使用メモリ 3,288 KB
最終ジャッジ日時 2020-01-17 08:43:55

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 0 ms
3,120 KB
99_system_test2.txt AC 0 ms
3,268 KB
99_system_test3.txt AC 0 ms
3,212 KB
sample1.txt AC 4 ms
3,264 KB
sample2.txt AC 4 ms
3,208 KB
sample3.txt AC 0 ms
3,288 KB
system_test1.txt AC 0 ms
3,156 KB
system_test2.txt AC 0 ms
3,188 KB
system_test3.txt AC 4 ms
3,156 KB
system_test4.txt AC 4 ms
3,160 KB
system_test5.txt AC 0 ms
3,184 KB
system_test6.txt AC 0 ms
3,152 KB
system_test7.txt AC 0 ms
3,268 KB
system_test8.txt AC 0 ms
3,116 KB
system_test9.txt AC 4 ms
3,268 KB
test1.txt AC 4 ms
3,284 KB
test2.txt AC 4 ms
3,276 KB
test3.txt AC 0 ms
3,184 KB
test4.txt AC 0 ms
3,272 KB
test5.txt AC 4 ms
3,268 KB
test6.txt AC 4 ms
3,276 KB
test7.txt AC 4 ms
3,156 KB
test8.txt AC 0 ms
3,208 KB
test9.txt AC 0 ms
3,164 KB
test10.txt AC 0 ms
3,192 KB
test11.txt AC 0 ms
3,132 KB
test12.txt AC 4 ms
3,188 KB
test13.txt AC 4 ms
3,280 KB
test14.txt AC 4 ms
3,132 KB
test15.txt AC 0 ms
3,128 KB
test16.txt AC 0 ms
3,200 KB
test17.txt AC 0 ms
3,188 KB
test18.txt AC 4 ms
3,264 KB
test19.txt AC 4 ms
3,196 KB
test20.txt AC 4 ms
3,204 KB
テストケース一括ダウンロード

ソースコード

diff #
#define _CRT_SECURE_NO_WARNINGS
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
//#define endl "\n"
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator<<(ostream & os, vector<T> const &);
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }
template<class T, class U> ostream & operator<<(ostream & os, pair<T,U> const & p){ return os << "(" << p.first << ", " << p.second << ") "; }
template<class T> ostream & operator<<(ostream & os, vector<T> const & v){ rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os; }
template<class T> inline bool chmax(T & x, T const & y){ return x<y ? x=y,true : false; }
template<class T> inline bool chmin(T & x, T const & y){ return x>y ? x=y,true : false; }
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<mt(__VA_ARGS__)<<" ["<<__LINE__<<"]"<<endl)
#else
#define dump(...)
#endif
// ll const mod = 1000000007;
// ll const inf = 1LL<<60;

// スパソ
int longest_palindrome(char *text, int n) {
    int rad[2*n], i, j, k;
    for (i = 0, j = 0; i < 2*n; i += k, j = max(j-k, 0)) {
        while (i-j >= 0 && i+j+1 < 2*n && text[(i-j)/2] == text[(i+j+1)/2]) ++j;
        rad[i] = j;
        for (k = 1; i-k >= 0 && rad[i]-k >= 0 && rad[i-k] != rad[i]-k; ++k)
            rad[i+k] = min(rad[i-k], rad[i]-k);
    }
    return *max_element(rad, rad+2*n); // ret. centre of the longest palindrome
}

char c[100];
signed main(){
    cin >> c;
    int n = strlen(c);
    int a = longest_palindrome(c,n-1);
    int b = longest_palindrome(c+1,n-1);
    cout << max(a,b) << endl;
}
0