# クラス StringAlgorithm - - - 文字列アルゴリズム詰め合わせです。 文字列に関する様々なアルゴリズムが入っています。 ## suffixArray ```Java // (1) public static int[] suffixArray(java.lang.String s) // (2) public static int[] suffixArray(char[] s) // (3) public static int[] suffixArray(int[] s) // (4) public static int[] suffixArray(int[] s, int upper) ``` 長さ $n$ の文字列 `s` のSuffix Arrayとして、長さ $n$ のint配列を返す。 Suffix Array `sa`は $(0,1,\ldots ,n-1)$ の順列であって、各 $i=0,1,\cdots , n-2$ について `s[sa[i]..n) < s[sa[i+1]..n)` を満たすもの。 ### 制約 - $0\le n\le 10^8$ - (4) $0\le \mathrm{upper}<10^8$ - (4) $s$ のすべての要素 $x$ について $0\le x\le \mathrm{upper}$ ### 計算量 - (1) (2) $O(n)$ - (3) 時間 $O(n\log n)$ 空間 $O(n)$ - (4) $O(n+\mathrm{upper})$ ## lcpArray ```Java // (1) public static int[] lcpArray(java.lang.String s, int[] sa) // (2) public static int[] lcpArray(char[] s, int[] sa) // (3) public static int[] lcpArray(int[] s, int[] sa) ``` 長さ $n$ の文字列 `s` のLCP Arrayとして、長さ $n-1$ の配列を返す。$i$ 番目の要素は `s[sa[i]..n), s[sa[i+1]..n)` の LCP(Longest Common Prefix) の長さ。 ### 制約 - `sa` は `s` のSuffix Array - $1 \le n \le 10^8$ ### 計算量 - $O(n)$ ### 使用例 [[https://atcoder.jp/contests/practice2/submissions/16585271]] ## zAlgorithm ```Java // (1) public static int[] zAlgorithm(java.lang.String s) // (2) public static int[] zAlgorithm(char[] s) // (3) public static int[] zAlgorithm(int[] s) ``` 入力の長さを $n$ として、長さ $n$ の配列を返す。 $i$番目の要素は `s[0..n)` と `s[i..n)` のLCP(Longest Common Prefix)の長さ。 ### 制約 - $0\le n\le 10^8$ ### 計算量 - $O(n)$