- LCP array - Wikipedia
- LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
- 接尾辞配列を作った後、隣接してる文字列のLCP(longest common prefix)の長さを記録しておく
- Kasai法でO(N)
- 『部分語計数問題の接尾辞配列を用いた高速アルゴリズム』PDF
- https://naoyat.hatenablog.jp/entry/construct-suffix-array-and-lcp-in-linear-time
- Kasai法でO(N)
- 任意の2つの項目のLCP長は、その2つの間のLCP長の最小値に一致する
- この情報を使うと二分探索が高速化できる
- クエリ長Mの時、素朴なO(MlogN)がO(M+logN)になる