It contains string algorithms.
Let s
be a string.
We denote the substring of s
between $a$-th and $b - 1$-th character by s[a..b)
.
(1) vector<int> suffix_array(string s)
(2) vector<int> suffix_array<T>(vector<T> s)
(3) vector<int> suffix_array(vector<int> s, int upper)
Given a string s
of length $n$, it returns the suffix array of s
.
Here, the suffix array sa
of s
is a permutation of $0, \cdots, n-1$ such that s[sa[i]..n) < s[sa[i+1]..n)
holds for all $i = 0,1, \cdots ,n-2$.
Constraints
T
is int
, uint
, ll
, or ull
.Complexity
(1) vector<int> lcp_array(string s, vector<int> sa)
(2) vector<int> lcp_array<T>(vector<T> s, vector<int> sa)
Given a string s
of length $n$, it returns the LCP array of s
.
Here, the LCP array of s
is the array of length $n-1$, such that the $i$-th element is the length of the LCP (Longest Common Prefix) of s[sa[i]..n)
and s[sa[i+1]..n)
.
Constraints
sa
is the suffix array of s
.T
is int
, uint
, ll
, or ull
.Complexity
(1) vector<int> z_algorithm(string s)
(2) vector<int> z_algorithm<T>(vector<T> s)
Given a string of length $n$, it returns the array of length $n$, such that the $i$-th element is the length of the LCP (Longest Common Prefix) of s[0..n)
and s[i..n)
.
Constraints
T
is int
, uint
, ll
, or ull
Complexity