Suffix Treeで解ける有名っぽい問題

はじめに

Suffix Treeで解ける有名っぽい問題(Gusfield本に載ってるやつ)の中で競プロで使う事がありそうなものの解法をまとめる 記法とか定義とかがものすごくガバガバなのは許してください

定義

以下を適当に定義する

  • 文字について

    • $\$$ と $\$_i (1 \leq i)$ を区切り文字とし、入力で与えられていないような入力中のどの文字よりも辞書順で小さい文字とする
  • 文字列 $S$ について

    • $S[i, j]$ を $S$ の $i$ 文字目から $j$ 文字目までの文字列とする ($i > j$ なら $S[i, j]$ は空文字列)
  • Suffix Tree, Generalized Suffix Tree中のノード $v$ について

    • 根と $v$ のパスが表す文字列を ${\rm str} (v)$ とする

    • ${\rm depth} (v) = |{\rm str} (v)|$ とする

  • Suffix Arrayについて

    • ${\rm SA}_S$ を $S\$$ のSuffix Arrayとする(特に区別する必要がなければ ${\rm SA} _ S = {\rm SA }$ と省略して表記する)
  • Suffix Treeについて

    • ${\rm ST} (S)$ を $S\$$ を表現するSuffix Treeとする
  • Suffix Tree中のノード $v$ について

    • ${\rm str} (v) = S[i, i + {\rm depth} (v)]$ であるような適当な $i$ に対して、 ${\rm pos} (v) = i$ とする
  • Generalized Suffix Treeについて

    • ${\rm GST} (\mathcal{S})$ を $ S_1 \$_1 S_2 \$_2 \dots S_{|\mathcal{S}|} \$_{|\mathcal{S}|}$ を表現するGeneralized Suffix Treeとする
  • Generalized Suffix Tree中のノード $v$ について

    • ${\rm str} (v) = S_i[j, j + {\rm depth} (v)]$ であるような適当な $i, j$ に対して、 ${\rm label} (v) = i, {\rm pos} (v) = j$ とする

問題

Maximal repeats

定義

  • 文字列 $T$ と$1 \leq i \leq j \leq |S|$ に対し $T[i,j] = T[i',j'] ,\ T[i-1,j] \neq T[i'-1,j'] ,\ T[i,j+1] \neq T[i',j'+1], (i, j) \neq (i', j')$ を満たす $(i', j')$ が存在する場合、 $(i, j)$ を $T$ の maximal repeatと定義する

問題概要

  • 文字列 $S$ が与えられる

  • $S$ の全てのmaximal repeat $(i, j)$ についての $S[i, j]$ の集合 $\mathcal{S}$ を求める

  • 文字列を出力すると出力サイズが $ \Theta ( |S| ^ 2 )$ になる事があるため、 $S[l,r] \in \mathcal{S}$ であるような $(l, r)$ の集合の形で表す

解法

  • ${\rm ST} (S)$ の内部節点を全て見る

  • 内部節点 $v$ の子孫であり ${\rm pos} (u) = k$ であるような葉 $u$ について $S_{k - 1}$ を調べ、これが全て一致していなければ $(k, k + {\rm depth} (v))$ はmaximal repeatになる

  • 子孫となる葉の集合は $\rm SA$ 中の区間になるため、$V [i] = S_{{\rm SA} [i] -1}$ であるような配列 $V$ 中で種類数が$1$になる区間を前計算しておけば解ける

  • 列挙する際は全ての $v$ に対して適当な $u$ を選んで $(k, k + {\rm depth} (v))$ を報告すればよい

Supermaximal repeats

定義

  • $(i, j)$ が文字列 $T$ のmaximal repeatであり、 $(i, j) \neq (i', j')$ である任意の $T$ のmaximal repeat $(i', j')$ と非負整数 $l, r$ に対して $(i'+l, j'-r) \neq (i, j)$ が成り立つ時、$(i, j)$ を $T$ のsupermaximal repeatと定義する

問題概要

  • 文字列 $S$ が与えられる

  • $S$ の全てのsupermaximal repeat $(i, j)$ についての $S[i, j]$ の集合 $\mathcal{S}$ を求める

  • maximal repeat と同様、$( l, r )$ の集合の形で表す

解法

  • maximal repeatと同様に ${\rm ST} (S)$ を考える

  • 子が全て葉である内部節点 $v$ の子で ${\rm pos} (u) = k$ であるような葉 $u$ について $ S _ { k - 1 } $ が全て異なっているならば $(k, k + {\rm depth} (v))$ はsupermaximal repeatになるため、それを報告すればよい

  • $S_ { k - 1 } $ が全て異なるような区間はしゃくとり法で前計算できる

Longest common substring

定義

  • 文字列集合 $\mathcal{S} = \{ S_1, S_2, \dots S_m \}$ に対して、$S_i[l_i, r_i] = T$ であるような $(l_i, r_i) \ (1 \leq l_i \leq r_i \leq |S_i|)$ が存在するような $S_i$ の個数が $k$ 以上である時、文字列 $T$ を $\mathcal{S}$ の種類数 $k$ のlongest common substringと定義する

問題概要

  • 文字列集合 $\mathcal{S}$ が与えられる

  • $1 \leq k \leq |\mathcal{S}|$ を満たす全ての $k$ に対して種類数 $k$ のlongest common substringの最大の長さを求める

解法

  • ${\rm GST} (\mathcal{S})$ を構築する

  • 内部節点 $v$ の子孫であるようなノード $u$ についての ${\rm label} (u)$ の集合を求め、集合の要素数が $k$ 以上である時、${\rm str} (v)$ は種類数 $k$ のlongest common substringである

  • これはmaximal repeatと同様に区間種類数になって、解ける

All-pairs suffix-prefix matching

定義

  • 文字列の組 $(S, T)$ に対して $S[1, k] = T[|T| + 1 - k, |T|]$ を満たす最大の $k\ (0 \leq k \leq {\rm min} (|S|, |T|))$ をsuffix-prefix matchingと定義する

問題概要

  • $ M $ 個の文字列からなる文字列集合 $\mathcal{S}$ が与えられる

  • $1 \leq i , j \leq M $ を満たす全ての $(i, j)$ の組について、$(S_i, S_j)$ のsuffix-prefix matchingを求める

解法

  • ${\rm GST} (\mathcal{S})$ を構築する

  • ノード $v$ の子にラベル $\$_k$ の辺が存在する時、ノード $v$ をk-terminateと呼ぶ

  • ${\rm str} (v) = S_i[1, k]\ (1 \leq k \leq |S_i|)$ であるノード $v$ がj-terminateである時、$(S_i, S_j)$ のsuffix-prefix matchingは $k$ 以上になる

  • stackを $|\mathcal{S}|$ 個管理してDFSをする 今見ているノード $v$ がj-terminateである場合、 $j$ 個目のstackに ${\rm depth} (v)$ をpushする(探索終了時にpopする)

  • ${\rm label} = i, {\rm pos} = 1$ であるようなノードに到達した時に、$1 \leq j \leq |\mathcal{S}|$ を満たす全ての $j$ に対して $j$ 番目のstackのtopを確認すればいい