acl_cpp.string

from acl_cpp.string import suffix_array, lcp_array, z_algorithm

string.suffix_array

# (1) vector<int> suffix_array(string s)
def suffix_array(s: str) -> list[int]

# (2) vector<int> suffix_array<ll>(vector<ll> s)   
def suffix_array(s: list[int]) -> list[int]

# (3) vector<int> suffix_array(vector<int> s, int upper)
def suffix_array(s: list[int], upper: int) -> list[int]

Let \(n = \text{len}(s)\), returns an array sa of length \(n\) as defined below.

sa is a permutation of \((0, 1, \ldots, n-1)\).
s[sa[i]:] < s[sa[i+1]:] holds.

Constraints

(2) \(-2^{63} \leq s[i] \lt 2^{63}\)
(3) \(0 \leq s[i] \leq \text{upper} \lt 2^{31}\)

Complexity

(1) \(O(n)\)
(2) \(O(n \log n)\) time, \(O(n)\) space
(3) \(O(n + \mathrm{upper})\)

string.lcp_array

# (1) vector<int> lcp_array(string s, vector<int> sa)
def lcp_array(s: str, sa: list[int]) -> list[int]

# (2) vector<int> lcp_array<ll>(vector<ll> s, vector<int> sa)
def lcp_array(s: list[int], sa: list[int]) -> list[int]

Let \(n = \text{len}(s)\), returns an array lcp of length \(n-1\) as defined below.

lcp[i] is the length of the LCP (Longest Common Prefix) of s[sa[i]:] and s[sa[i+1]:].

Constraints

sa is the Suffix Array of s.
- Behavior is undefined if this is not satisfied.

Complexity

\(O(n)\)

string.z_algorithm

# (1) vector<int> z_algorithm(string s)
def z_algorithm(s: str) -> list[int]

# (2) vector<int> z_algorithm<ll>(vector<ll> s)
def z_algorithm(s: list[int]) -> list[int]

Let \(n = \text{len}(s)\), returns an array z of length \(n\) as defined below.

z[i] is the length of the LCP (Longest Common Prefix) of s and s[i:].

Constraints

(2) \(-2^{63} \leq s[i] \lt 2^{63}\)

Complexity

\(O(n)\)

Examples

from acl_cpp.string import suffix_array

s = "missisippi"
sa = suffix_array(s)

answer = [
    "i",
    "ippi",
    "isippi",
    "issisippi",
    "missisippi",
    "pi",
    "ppi",
    "sippi",
    "sisippi",
    "ssisippi",
]

for i, t in zip(sa, answer):
    assert s[i:] == t

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_i

from acl_cpp.string import suffix_array, lcp_array

s = input()
n = len(s)
sa = suffix_array(s)
lcp = lcp_array(s, sa)

print(n * (n + 1) // 2 - sum(lcp))