LCP Array の追加

[noss3885]

概要

• Longest Common Prefix Array を求めるアルゴリズム。Suffix Array の計算を前提とする。
  • Suffix Array $sa$ に対して $sa[i]$ と $s[i+1]$ の共通接頭辞の長さを各 $i$ について求める。
• 計算量: 長さ $N$ の文字列に対して $O(N)$

参考資料

• https://ei1333.github.io/luzhiled/snippets/string/suffix-array.html
• https://github.com/beet-aizu/library/blob/master/string/longestcommonprefix.cpp

テスト問題

• https://judge.yosupo.jp/problem/number_of_substrings