読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるAho-Corasick問題まとめ

Aho-Corasick法とは

問題(上に行くほど入門)

yukicoder No.430 文字列検索

http://yukicoder.me/submissions/151655
一番典型的な形。

UVA 10679 I Love Strings!!

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1620
これも典型的な形。


これ以下の問題は作った木上でのDP

AOJ 2212 盗まれた宝石

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2212
禁止文字状態をDPとして持っておき、判定していく

AOJ 2257 Sakura Poetry

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257
上と違って最短経路系のDPではなくて、数え上げのDPであり、Aho-Corasick的にはあまり変わらないけれど、他に色々考えることがあり、やや難しい

TopCoder SRM709 Med Softmatch

https://community.topcoder.com/stat?c=problem_statement&pm=14531&rd=16853
ぜんぜん分からない。

余談

以前、この問題http://codeforces.com/contest/750/problem/Eオートマトン+DPをしていて、
どういう思考の流れでこういう解法が思いつくのか分からなかったですが、
このAho-Corasick法的な手法から考えていけば思いつくのかな?
上の問題の解説はpekempeyさんのブログが最強
http://pekempey.hatenablog.com/entry/2016/12/31/162212#E-New-Year-and-Old-Subsequence