接尾辞配列

競プロの接尾辞配列の問題

接尾辞配列の構築

検索

文字列検索

文字列Sに文字列Tが出現するかは，接尾辞配列を2分探索することでO(|T| log |S|)で計算できる．

文字列の出現位置

2分探索を2回することで接尾字配列上で探索文字列の開始位置と終了位置を計算できる．

部分文字列

出現頻度

  • CS Academy
    • 文字列Sが与えられる．Sの部分文字列のうち出現頻度が最も多いものを求めよ．

異なる部分文字列の数・文字数

長さKの部分文字列の数

  • SPOJ.com - Problem ADACLEAN

    • 文字列Sが与えられる．distinctな長さKの部分文字列の数を求めよ．

  • SPOJ.com - Problem NSUBSTR

    • 文字列Sが与えられる．F(x)を長さxの部分文字列の最大の出現回数とする．1から|S|までのF(x)を求めよ．

K番目の部分文字列

  • SPOJ.com - Problem SUBLEX
    • 文字列Sが与えられる．文字列Sのdistinctな部分文字列を昇順に並べたときのK番目の文字列を求めよ．

ある文字からはじまる部分文字列の数

  • SPOJ.com - Problem ADASTRNG
    • 文字列Sが与えられる．aからzまでの各文字について，その文字からはじまるdistinctな部分文字列の個数を求めよ．

共通部分文字列

最長共通部分文字列

開始位置iとjの共通部分文字列

  • SPOJ.com - Problem VOTAS
    • 文字列Sが与えられる．Sのprefixの集合をPとする．また，SのsuffixであるS_iのprefixの集合をP_iとする．Kが与えられるので，PとP_iの共通集合の数がK以上であるS_iの数を求めよ．

回文

  • SPOJ.com - Problem LPS
    • 文字列が与えられる．文字列に含まれる最長の回文の長さを求めよ．

rotation

コード

https://github.com/MitI-7/CompetitiveProgramming/tree/master/SphereOnlineJudgegithub.com

未整理

参考