String

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).

suffix_array

(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

Complexity

lcp_array

(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

Complexity

z_algorithm

(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

Complexity

Examples

How to Use

#include <atcoder/string> #include <string> #include <vector> using namespace std; using namespace atcoder; int main() { string s = "missisippi"; vector<int> sa = suffix_array(s); vector<string> answer = { "i", "ippi", "isippi", "issisippi", "missisippi", "pi", "ppi", "sippi", "sisippi", "ssisippi", }; assert(sa.size() == answer.size()); for (int i = 0; i < int(sa.size()); i++) { assert(s.substr(sa[i]) == answer[i]); } }

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

#include <atcoder/string> #include <iostream> #include <string> #include <vector> using namespace std; using namespace atcoder; int main() { static char buf[500'001]; scanf("%s", buf); string s = buf; vector<int> sa = suffix_array(s); long long answer = 1LL * s.size() * (s.size() + 1) / 2; for (auto x : lcp_array(s, sa)) { answer -= x; } printf("%lld\n", answer); return 0; }