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

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

hamayanhamayan's blog

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

Suffix Array

  • 接尾辞配列
  • 全文探索、パターンマッチングに使える
  • Suffix Array構築後にLCPを併用すると更に高速化できる

LCP

  • Longest Common Prefix
  • ある2つの文字列について接頭語がどれだけ一致しているか
  • 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列の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が必要になってくるまでの道のりが分かりにくい。
使う場面は「ある区間の文字列の接尾語の辞書順最小のものが知りたい」

yukicoder No.515 典型LCP

http://yukicoder.me/problems/no/515
LCPを利用