CodeChef May Challenge 2020 - Buying a New String

• 問題
• AC

たくさん解かれているのに部分点すらわからないので、書いたことのない文字列アルゴリズムだろうなと検討をつける。Aho-Corasickがいちばんそれっぽいので、貼るととりあえず部分点が取れた。

$|A||B|$個の文字列間で遷移の共通部分が多いことを利用できれば満点が取れそう。そして、そのためにはAho-Corasickをちゃんと理解する必要がありそう。しかし、ei1333さんのコードを見ていても理屈がよくわからないので、明らかな性質だけでなんとかすることにした:

• Aho-Corasickのマッチは部分文字列の一致をひとつずつカウントする。つまり、まとめてカウントしたりはできないので、素朴にやるとマッチする文字列の長さに対して${O}(N^2)$になる。とりあえず、トライ木を作ったらノード毎に重みの和をまとめておいたほうがよさそう。たぶんそれでオーダーも落ちる。
• Aho-Corasickの状態は今いるノードだけで決まる。つまり、ノードが同じで以降の文字列が同じならその後の遷移はすべて同じ。

以上に基づくと、次の配列を作っておけばよいはず:

$\operatorname{cumul}_A[i] := A$の区間$[0, i)$を走査した後のスコア
$\operatorname{node}_A[i] := A$の区間$[0, i)$を走査した後のノード
$\operatorname{cumul}_B[i] := B$の区間$[0, i)$を走査した後のスコアを$0$として、そこから最後まで走査して得られるスコア。
$\operatorname{node}_B[i] := B$の区間$[0, i)$を走査した後のノード

$A, B$をそれぞれ$[0, i_1,), [i_2, \operatorname{length}(B))$で切った時のスコアは$\operatorname{cumul}_A[i_1]$に$\operatorname{node}_A[i_1]$から$B[i2, \operatorname{length}(B))$を走査して得られるスコアを足したものになるが、この途中で、$B$の位置$i$を走査する際にノードが$\operatorname{node}_B[i]$と一致していることが確認できたら$\operatorname{cumul}_B[i]$を足して打ち切ってよい。単語の長さが高々26なので、$i_1$からそれだけ遷移すれば一致するはず。計算量はたぶんアルファベットの数を$\alpha$として${O}(\alpha|A||B| + \sum_i S_i)$。

---

そしてまだAho-Corasickを理解していない……