Suffix Array

新しいアルゴリズムを学んだので自分用の備忘録．

Suffix Arrayとは

• 日本語では接尾辞配列
• ある文字列の全ての接尾辞を辞書順に並べたもの
• 例えば “coder” という文字列について考える
  接尾辞は “coder”, “oder”, “der” “er”, “r”, “”
  接尾辞配列は以下の通り

開始位置	接尾辞
5
0	coder
2	der
3	er
1	oder
4	r

• Suffix Arrayを使うと，長さnの文字列の中から長さmの文字列を[latex]\mathcal{O}(m\log{n})[/latex]で探索したりできる
• 競技プログラミングでもよく使うらしい (僕はまだ2問しか見たことない)

Suffix Arrayの構築

• 愚直に構築することを考える
  • ソートのための比較の回数は[latex]\mathcal{O}(n\log{n})[/latex]かかる
  • 比較は[latex]\mathcal{O}(n)[/latex]かかる
  • よって構築のオーダーは[latex]\mathcal{O}(n^2 \log{n})[/latex]
  • 競技プログラミング的には[latex]n=10000[/latex]くらいからアウトだと思われる
• その他の方法
  • SA-IS法 : [latex]\mathcal{O}(n)[/latex]
    • はやい，競技プログラミング的にオーバーキル気味
    • コード長い
    • 理解には論文を読む必要があるらしい…
  • Manber&Myers : [latex]\mathcal{O}(n \log^2 n)[/latex]
    • 競技プログラミング的に丁度いいはやさ
    • コード短い
    • 蟻本を読めば理解可能

• 今回はManber&Myersについて学ぶことにする

Manber&Myers

• 接尾辞配列の最初の1文字でソート→2文字でソート→4文字でソート…
• すでにソート済みの情報を使うので1回のソートは[latex]\mathcal{O}(n\log{n})[/latex]
• よって[latex]\mathcal{O}(n \log^2 n)[/latex]
• 蟻本の説明とコードを見ても理解に時間かかったのでコードにコメントをつけた