まず、印をつけた文字が隣り合ってはいけないという制約を外した以下の問題を考えてみましょう。

\(S\) の空文字列でない部分文字列の個数を求めよ。ただし、部分文字列とは元の文字列から \(0\) 文字以上取り除き残った文字を元の順番で並べたものである。

ここで重要なのは、異なる削除の方法によって同じ部分文字列が得られる可能性があるということです。この重複を避けながら部分文字列を数え上げる”部分列DP”と呼ばれる手法を紹介します。

以下のようなDPを考えます。

• \(dp_i\) := 文字列 \(S\) の \(1\) 文字目から \(i\) 文字目までの部分から得られる部分文字列のうち \(i\) 文字目は必ず使うようなものの個数

ただし、空文字列に対応して \(dp_0=1\) とします。遷移は次のようになります。

• \(dp_i = \sum_{j=0}^{i-1} dp_j\)

このままでは同じ部分文字列を重複して数えてしまうので、遷移を以下のようにします。

• \(k\) を \(S_i=S_k\) かつ \(k<i\) を満たす最大の整数として（存在しない場合 \(k=0\)）、\(dp_i=\sum_{j=k}^{i-1}dp_j\)

直感的には \(S_k=S_i\) ならば、ある \(j(<k)\) について \(S_j\) のすぐ後に \(S_i\) をつなげるのは無駄（\(S_j\) の後に \(S_k\) をつなげればよい）なので重複を避けるため禁止します。実はこの工夫だけで重複せずに全ての部分文字列を数え上げることができます。

計算量は一見 \(O(|S|^2)\)に見えますが、文字の種類数を \(σ\) としたとき、累積和を用いれば \(O(|S|)\)、用いなくとも \(O(σ|S|)\) で十分高速です。

この発想で元の問題を解くことができます。\(dp_0=1\)、\(dp_1=0\) とします。漸化式は以下です。

• \(k\) を \(S_i=S_k\) かつ \(k<i\) を満たす最大の整数として（存在しない場合 \(k=0\)）、\(dp_{i+1}=\sum_{j=k}^{i-1}dp_j\)

実装例 (C++)

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

int main(){
    string S; cin >> S;
    int N = S.size();
    vector<long long> dp(N+2); dp[0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = i-1; ; j--){
            dp[i+2] = (dp[i+2] + dp[j+1]) % 1000000007;
            if(j == -1 || S[j] == S[i]) break;
        }
    }
    long long ans=0;
    for(int i = 2; i < N+2; i++) ans += dp[i];
    cout << ans%1000000007 << endl;
}