AGC 037 B - First Second

• 問題
• AC

文字列を反転して条件を言い換えると、文字列$s, t, (|s| \le |t|)$に関する問題の条件は次のようになる。(添え字はPython風に表している)

1. $t$のprefixに$s$の最後の1文字を除いたもの$s[:-1]$が含まれ、
2. さらに$s$の最後の1文字$s[-1]$が$t$のそれ以降に存在する

1つ目の条件だけ考える場合、事前にTrieを作っておけば$s[:-1]$をprefixとして含むような文字列の総数は高速に数えられる。この時、$s[:-1]$をTrieで辿った際の終端ノードに2つ目の条件に関する情報があれば、うまく数えられそうに見える。具体的には、そのノードの部分木に含まれる文字列で$s[-1]$を含んでいるものの数が記録されていれば、2つ目の条件も満たすものが数えられる。

そこで、配列$\operatorname{dp_v}$を$\operatorname{dp_v}[c] :=v$の子に属する文字列で以降に文字$c$を含むものの総数、と定めて、Trieの各ノードに持たせればよい。

アルファベットのサイズを$\alpha$とするとき、この$\operatorname{dp}$配列は各ノードについてならし${O}(\alpha)$で作れるので、全体の計算量は${O}(\alpha\sum_i S_i)$。（一つの子ノードについて、親への遷移はちょうど1回で、遷移の計算量が${O}(\alpha)$。）