AtCoder ABC 320 B - Longest Palindrome (灰色, 200 点)

最長回文を求める問題！

• 問題へのリンク

問題概要

文字列 が与えられる。 の連続する部分文字列のうち、回文であるものについて、最長の長さを求めよ。

考えたこと

この問題は次の 2 ステップに分かれている。

---

1. の連続する部分文字列を全種類抜き取る
2. それら文字列が回文であるかどうかを判定する

---

1 については、定石がある。たとえば、文字列 が "algorithm" のとき、これは 9 文字である。この文字列の両端と隙間を合わせると 10 箇所ある。これらに 0, 1, 2, ..., 9 と番号を振る。このとき、これら 10 個の番号から 2 つ選ぶと、下図のように部分文字列が決まる。たとえば、番号 3 と 7 を選ぶと、部分文字列 "orit" に対応する。

これら部分文字列をすべて調べるのは次のように実装できる。ただし、文字列 の長さを とする。

for (int i = 0; i < N; ++i) {
     for (int j = i + 1; j <= N; ++j) {
         string sub = "";
         for (int k = i; k < j; ++k) sub += S[k];
         
         // 部分文字列 sub について調べる

    }
}

次に、2 の「回文判定」について。これは、次のように実装するのが早いと思う。

// T が回文かどうかを判定する関数
bool is_palindrome(string T) {
    int M = (int)T.size();
    
    // i は T の先頭から右へ、j は T の末尾から左へ
    for (int i = 0, j = M-1; i < j; ++i, --j) {
        if (T[i] != T[j]) return false;
    }
    return true;
}

以上を組み合わせると正解できる。

コード

#include <bits/stdc++.h>
using namespace std;

// 文字列 T が回文かどうかを判定する関数
bool is_palindrome(string T) {
    int M = (int)T.size();
    
    // i は T の先頭から右へ、j は T の末尾から左へ
    for (int i = 0, j = M-1; i < j; ++i, --j) {
        if (T[i] != T[j]) return false;
    }
    return true;
}

int main() {
    string S;
    cin >> S;
    int N = (int)S.size();
    
    int res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            string sub = "";
            for (int k = i; k < j; ++k) sub += S[k];
            
            // 部分文字列 sub について調べる
            if (is_palindrome(sub)) res = max(res, j - i);
        }
    }
    cout << res << endl;
}