ABC104 D: We Love ABCを解いたのだけど， 解説を読んでみると別解だったので解法を残しておく．
提出したコードは下記に．
提出 #14942063 - AtCoder Beginner Contest 104
入力を s とする．
関数 fn(s, t, i, j) を以下のように定義する．
fn(s, t, i, j) 文字列sのi番目以降をs[i:]とする． s[i:] の部分文字列として t[j:] は何回現れるか
下記の文字列をそれぞれ，t_k (0 <= k < 8)とする．
- "ABC"
- "AB?"
- "A?C"
- "A??"
- "?BC"
- "?B?"
- "??C"
- "???"
文字列 s 中に現れる '?' の個数を q, 文字列 t 中に現れる '?' の個数を r とする．
それぞれの k について，下記を求め，足し合わせると解となる．
fn(s, t_k, 0, 0) * 3^(max(0, q - r))
全体で O(|s|) である．
3 <= |s| <= 10^5 であるため，これは制限時間の2秒に十分間に合う．
関数 fn(s, t, i, j) は，i, j をメモ化すると O(|s| |t|) となるが，
|t| は常に3文字であるため，定数項とみなした．
k についても (0 <= k < 8) であるため，同様に定数項とした．
問題では，
10^9+7で割った余りを出力してください
とあるので，注意が必要である． 詳細については，本記事では割愛する．
また， t_k についてそれぞれ処理するとき，ビット全探索と呼ばれるテクニックを用いると，
より容易に実装が可能である．