天下一プログラマーコンテスト2016本戦 C - たんごたくさん

• 問題
• AC (Trie)
• AC (ローリングハッシュ)

$S := a_0a_1...,a_{n-1}$の連続部分列$a_la_{l+1}...a_{r-1}$を$S[l, r)$と書くことにする。文字列$S[i, n)$に対して問題の操作を行った時の最大値を$f(i)$とするとき、

$f(i) = \max_{i < k \le 200} \bigr(S[i, k)の重さ + f(k) \bigl)$

だから、DPして$f(0)$を求めればそれが答えである。（ただし、$P$に含まれない単語の重さは$0$とする。）$S[i, k)$の重さを求める部分で、部分列が$P$に含まれているかを素朴に判定すると間に合わないので、Trieやローリングハッシュを使う。

---

Trieの例題として解いたのだが、よく見るとローリングハッシュでも問題なかった。ただ、後者はかなり重い。