はまやんはまやんはまやん

hamayanhamayan's blog

Concatenated Palindrome [CODE THANKS FESTIVAL 2017 B]

https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_b

解法

https://code-thanks-festival-2017-open.contest.atcoder.jp/submissions/1825593

後ろに追加する文字列は、追加される文字列の先頭部分との回文関係を保つ必要がある。
そのため、後ろにi文字追加する場合は、文字列Sを反転させて後ろからi文字追加するしかない。
よって、Tの候補となるのは、高々50通りしかないので、全探索しよう。
 
チェックのために「check(s) := 文字列sが回分か」を用意しよう。
対応する文字が同じであるかを愚直に見ていく関数である。
 
C++での実装。
文字列の反転にはreverse、後ろからi文字取ってくるのはsubstrでやる。

string S, T; int N;
//---------------------------------------------------------------------------------------------------
int check(string s) {
    int n = s.length();
    rep(i, 0, n / 2) if (s[i] != s[n - 1 - i]) return 0;
    return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
 
    T = S;
    reverse(T.begin(), T.end());
 
    int ans = 0;
    rep(i, 0, N + 1) {
        string cand = S + T.substr(N - i);
        if (check(cand)) {
            printf("%d\n", i);
            return;
        }
    }
}