String

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

文字列 s の $a$ 番目から $b - 1$ 番目の要素のsubstringを、s[a..<b]と表記します。

suffix_array

(1) suffix_array(string s):seq[int]
(2) suffix_array[T](s:seq[T]):seq[int]
(3) suffix_array(s:seq[int], upper:int):seq[int]

長さ $n$ の文字列 s のSuffix Arrayとして、長さ $n$ の vector を返す。 Suffix Array sa は $(0, 1, \dots, n - 1)$ の順列であって、各 $i = 0,1, \cdots ,n-2$ について s[sa[i]..<n] < s[sa[i+1]..<n] を満たすもの。

制約

$0 \leq n \leq 10^8$
(2) T は int, uint, ll, ull
(3) $0 \leq \mathrm{upper} \leq 10^8$
(3) $s$ のすべての要素 $x$ について $0 \leq x \leq \mathrm{upper}$

計算量

(1) $O(n)$
(2) 時間 $O(n \log n)$ 空間 $O(n)$
(3) $O(n + \mathrm{upper})$

lcp_array

(1) lcp_array(s:string, sa:seq[int]):seq[int]
(2) lcp_array[T](s:seq[T], sa:seq[int]):seq[int]

長さ $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 \leq n \leq 10^8$
(2): T は int, uint, ll, ull

計算量

$O(n)$

z_algorithm

(1) z_algorithm(s:string):seq[int]
(2) z_algorithm[T](s:seq[T]):seq[int]

入力の長さを $n$ として、長さ $n$ の配列を返す。 $i$ 番目の要素は s[0..<n]とs[i..<n]のLCP(Longest Common Prefix)の長さ。

制約

$0 \leq n \leq 10^8$
(2): T は int, uint, ll, ull

計算量

$O(n)$

使用例

How to Use

import atcoder/string let s = "missisippi" let sa = suffix_array(s) let answer = [ "i", "ippi", "isippi", "issisippi", "missisippi", "pi", "ppi", "sippi", "sisippi", "ssisippi", ] assert sa.len == answer.len for i in 0..<sa.len: assert s[sa[i]..^1] == answer[i]

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

include atcoder/header import atcoder/string let s = nextString() sa = suffix_array(s) var answer = s.len * (s.len + 1) div 2 for x in lcp_array(s, sa): answer -= x echo answer