実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 658

問題概要

英大文字からなる文字列 $S$ が与えられる。整数の組 $(i, j, k)$ であって、以下の条件をともに満たすものの個数を求めよ。

$1 \leq i \lt j \lt k \leq |S|$
$S_i, S_j, S_k$ をこの順に結合して得られる長さ3の文字列が回文となる。

制約

$S$ の長さは $1$ 以上 $2 \times 10^5$ 以下。

考察

条件2が満たされるためには、 $S_i = S_k$ が成り立てば十分。つまり、 $S_j$ は任意に決められるということだ。

したがって、 $1 \lt j \lt |S|$ の範囲で $j$ を走査し、各 $j$ について $1 \leq i \lt j, \: j \lt k \leq |S|$ かつ $S_i = S_k$ を満たす整数組 $(i, k)$ を数え上げることを考える。

これを実現するためのデータ構造を考えよう。ここでは、以下の2つの配列を用意する。

$\mathrm{front}_{i, j} := S の1文字目から (i-1) 文字目までに出現する文字 j の個数$
$\mathrm{back}_{i, j} := S の (i+1) 文字目から |S| 文字目までに出現する文字 j の個数$

なお、 $j$ はアルファベット26文字に対応している。構築方法は以下の通り。

$i = 1, 2, \cdots, |S|$ について、
$i = 1$ ならば、 $j = 1, 2, \cdots, |S|$ について、 $\mathrm{back}_{1, S_j}$ を $1$ 増やす。
そうでないとき、
1. $\mathrm{front}_{i, j} = \mathrm{front}_{i - 1, j}, \: \mathrm{back}_{i, j} = \mathrm{back}_{i - 1, j}$ とする。
2. $\mathrm{front}_{i, S_{i-1}}$ を $1$ 増やし、 $\mathrm{back}_{i, S_i}$ を $1$ 減らす。これは $i$ を1増やすことによってずれた文字の分を考慮している。

ここまで分かれば、あとは答えを求めるだけ。アルファベット26文字の集合を $C$ とすると、最終的な答えは、

$\displaystyle \sum_{i = 2}^{|S| - 1} \sum_{j \in C} \mathrm{front}_{i, j} \cdot \mathrm{back}_{i, j}$

となる。

なお、以下のコードでは 0-indexed としている。

コード

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

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    string S;
    cin >> S;

    int l = S.size();
    vector<vector<ll>> front(l, vector<ll>(26, 0));
    vector<vector<ll>> back(l, vector<ll>(26, 0));
    rep(i, 0, l) {  
        if (i == 0) {
            rep(j, 1, l) {
                back[0][S[j] - 'A']++;
            }

            continue;
        }

        rep(j, 0, 26) {
            front[i][j] = front[i - 1][j];
            back[i][j] = back[i - 1][j];
        }
        front[i][S[i - 1] - 'A']++;
        back[i][S[i] - 'A']--;
    }
    
    ll ans = 0;
    rep(j, 1, l - 1) {
        rep(ch, 0, 26) {
            ans += front[j][ch] * back[j][ch];
        }
    }

    cout << ans << endl;
}