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

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

hamayanhamayan's blog

競技プログラミングにおけるSuffix Array+LCP問題まとめ

Suffix ArrayとLCP

問題

RUPC 2017 day1 D. Password(パスワード)

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp17Day1&pid=D
高速にパターンマッチングする必要があり、その場面で使用する。

DDPC 2016 C. アメージングな文字列は、きみが作る!

http://discovery2016-qual.contest.atcoder.jp/tasks/discovery_2016_qual_c
考察が長く、Suffix Arrayが必要になってくるまでの道のりが分かりにくい。
使う場面は「ある区間の文字列の接尾語の辞書順最小のものが知りたい」