Skip to content

Latest commit

 

History

History
105 lines (59 loc) · 2.51 KB

string.md

File metadata and controls

105 lines (59 loc) · 2.51 KB
Raw

String

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

suffix_array

(1) suffix_array(s)
(2) suffix_array(a)
(3) suffix_array(a, upper)

長さnの文字列sに対し、Suffix Arrayとして長さnのIntegerの配列を返します。

Suffix Array saは0 ... nの順列であって、各iについてs[sa[i]..n) < s[sa[i+1]..n)を満たします。

このSuffix Arrayの概念は一般の列にも適用でき、<=>演算子で比較可能な要素の配列aに対しても動作します。

  1. suffix_array(s)

内部でs.bytesによってバイト列に変換します。

制約

  • sは文字コード255以下の文字のみからなる文字列

計算量

O(|s|)

  1. suffix_array(a)

内部で、いわゆる座標圧縮を行います。要素は大小関係を保ったまま非負整数に変換されます。

制約

  • aの要素は互いに<=>演算子で比較可能

計算量

要素の比較が定数時間で行えるとして、O(|a| log |a|)

  1. suffix_array(a, upper)

制約

  • aはIntegerの配列

  • aの全ての要素xについて0≦x≦upper

計算量

O(|a| + upper)

lcp_array

lcp_array(s, sa)

長さnの文字列sのLCP Arrayとして、長さn-1のIntegerの配列を返します。i番目の要素はs[sa[i]..n)とs[sa[i+1]..n)のLCP ( Longest Common Prefix ) の長さです。

こちらもsuffix_arrayと同様一般の列に対して動作します。

制約

  • saはsのSuffix Array

  • (sが文字列の場合) sは文字コード255以下の文字のみからなる

計算量

O(|s|)

z_algorithm

z_algorithm(s)

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

制約

  • sの要素は互いに==演算子で比較可能

計算量

O(|s|)

Verified

参考