AOJ 2895 回文部分列 (AUPC 2018 day3 G)

すごく大好きな問題！
部分列を走査する考え方をちゃんとわかっていれば自然に解くことができる。

問題へのリンク

問題概要

文字列 が与えられる。 の部分文字列のうち回文となっているものが何通りあるか、1000000007 で割ったあまりで求めよ。

制約

• 
• は英小文字のみからなる

考えたこと

部分文字列を数え上げる問題をどのように解いていたかを思い出すと、

• 同じ部分文字列を生成する選び方のうち、選ぶ index の辞書順が最小になるものだけを考えて、それ以外は捨てる (できるだけ左寄せする)

という感じでやっていた。同じように

• 同じ回文部分文字列を生成する選び方のうち、両端になるべく寄せる

という風にやればよい。

ここでは、S を反転した文字列を T として

• ns[i][c] := S の i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
• nt[i][c] := T の i 文字目以降で最初に文字 c が登場する index (存在しないときは n)

とする。S と T とで共通する文字を左寄せしながら取って行くイメージの DP を立てる。

• dp[i][j] := S の i 文字目までと、T の j 文字目までをちょうど使ってできる回文の個数

として、

各アルファベット k に対して

dp[ ns[i][k] + 1 ][ nt[j][k] + 1 ] += dp[ i ][ j ]

という感じの遷移をすれば OK。

最後は「奇数長」の回文文字列を数え上げるために、i と j の間にある文字の種類をカウントして反映させていく。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int MOD = 1000000007;

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n + 1, vector<int>(26, n));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
        res[i][S[i] - 'a'] = i;
    }
    return res;
}

void add(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int main() {
    string S; cin >> S;
    int n = (int)S.size();
    string T = S;
    reverse(T.begin(), T.end());
    
    auto ns = calcNext(S);
    auto nt = calcNext(T);
    vector<vector<long long> > dp(n + 1, vector<long long>(n + 1, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 26; ++k) {
                int ni = ns[i][k];
                int nj = nt[j][k];
                if (ni + nj + 2 > n) continue;
                add(dp[ni + 1][nj + 1], dp[i][j]);
            }
        }
    }
    long long res = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; i + j <= n; ++j) {
            int num = 1;
            for (int k = 0; k < 26; ++k) if (ns[i][k] + 1 + j <= n) ++num;
            res = (res + dp[i][j] * num % MOD) % MOD;
        }
    }
    cout << res - 1 << endl;
}