回文検出(DP) - わりとよくある備忘録

回文検出は、以下の記事で書いたManacherのアルゴリズムを使えば $O(N)$ で解けるが、 $O(N^2)$ かければDPでも解くことが出来る。
DPの方が遅いが、コード的にはかなりシンプルに書けるのでメモしておく。

klee.hatenablog.jp
個人的にはManacherは偶数長の時とか、探索範囲の記述でバグを埋めそうで怖い。(ライブラリ化してるからよっぽど問題はないが)

どう解くか

以下のような2次元配列でDP配列の状態を定義する。

$dp[l][r]=s[l]+s[l+1]+...+s[r]$ が回文か?
このDPテーブルを以下のルールに従って埋めていく。

$i=j$ の時

必ず $s[i]==s[j]$ なので $dp[i][j]=true;$

$j-i=1$ の時

$s[i]==s[j]$ の時、 $dp[i][j]=true;$

$j-i>=2$ の時

まず $s[i]==s[j]$ である必要がある。ただし、この条件だけでは不十分で、これに加えて一個内側の部分文字列が回文であれば良い。
これは $A="abcba"$ と $B="abcca"$ の $l=0,r=4$ をそれぞれ考えればわかるが、 $B$ では明らかに内側である $l=1,r=3=>"bcc"$ が回文ではないので $l=0,r=4$ も回文にならないが、 $A$ は問題ない。
遷移の計算時、 $dp[i][j]$ の更新のためには $dp[i+1][j-1]$ が必要になるので、 $i$ は逆順で探索する必要があることに注意する。

実装

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int max_len = 0;
    int l, r;
    rrep(i, n) {//逆順
        reps(j, n, i) {
            if (j - i <= 1) {
                dp[i][j] = (s[i] == s[j]);
            } else {
                dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]);
            }
            if (dp[i][j] && max_len < j - i + 1) {
                max_len = j - i + 1;
                l = i;
                r = j;
            }
        }
    }
    string res = s.substr(l, r - l + 1);
    cout << res << endl;
    return 0;
}

簡単で安心。
計算量が許せばこっちを書きたい。