文字列アルゴリズム詰め合わせです。 文字列に関する様々なアルゴリズムが入っています。

// (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})$

// (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]]

// (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)$