- LCP array - Wikipedia
- Searching Suffix Array using LCP (Longest Common Prefix) - EchizenBlog-Zwei
- After creating suffix array, record the length of the LCP (longest common prefix) of the adjacent string.
- O(N) by the Kasai method
- A Fast Algorithm Using Suffix Arrays for the Subword Counting Problem” PDF.
- https://naoyat.hatenablog.jp/entry/construct-suffix-array-and-lcp-in-linear-time
- The LCP length of any two items matches the minimum LCP length between the two
- This information can be used to speed up the binary search.
- When query length M, naive O(MlogN) becomes O(M+logN)
This page is auto-translated from [/nishio/LCP array](https://scrapbox.io/nishio/LCP array) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.