接尾辞木（suffix tree）でできること。
- 文字列Sは部分文字列Tを持つか O(|T|)
- 接尾辞木でTの文字を順に辿れば良い。
- 文字列Sに含まれる部分文字列Tの位置を全て報告せよ。出現回数を occ
として O(|T|+occ)- 接尾辞木でTの文字を順に辿れば良い。根を除いて、次数 2 の内部頂点が存在しないことから、葉の数が occ の部分木の頂点数は O(occ) である。従って、根からのパスのラベルがTとなるような頂点の部分木についてDFSして葉を列挙すれば良い。
- 部分文字列の種類数
- Trieの根からのパスの個数、すなわち、Trieの頂点数に等しい。
- S[i:]とS[j:]のLCP O(1)
- S[i:]とS[j:]に対応する葉のLCA
- 各iについてΣ[j]|LCP(S[i:], S[j:])|の列挙 O(|S|)
（ABC213F）- (LCAの深さ+1)の和を上手く取れば良い。
- i=1,..,|S|に対して、i/2を中心とする極大な回文の列挙 O(|S|)
- S[i+1:]とrev(S)[|S|-i+1:]のLCPと言い換えられる。LCPはLCAでO(1)
- 2回以上現れる部分文字列のうち、最長であるもの
- 深さ最大の内部頂点に対応する部分文字列。
- S, T の最長共通部分文字列 O(|S|+|T|)
- S, T 両方の終端文字を子孫に持つ深さ最大の内部頂点のパスラベル
- S[1]+S[2]+..+S[k] の接尾辞木からS[i]の接尾辞木を構築せよ O(|S[i]|)
- S[i]の接頭辞を辞書順に並べる（接頭辞の葉を左から順に並べる）。隣り合う者同士のLCAでS[i]の接尾辞木の内部頂点が尽くされる。
- Sの各部分文字列に対して、T[1],T[2],..,T[k] のうち何個が部分文字列として含まれるか数えよ。 O(|S|+Σ|T[i]|)
- 特定の終端文字に着目する。その終端文字の頂点を DFS – in-order で並べて、隣り合う頂点の LCA を O(1) で計算する。各頂点について、部分木内の LCA に選ばれた頂点の個数は、max(0, (特定の終端文字の個数) – 1) に等しい。従って、和を取ると、(終端文字の個数) – (終端文字の種類数) となる。部分期に含まれる終端文字の個数は簡単に求まるので、終端文字の種類数も求まる。
- 文字列Sが円環状になっている。好きな位置で切ったときにできる辞書順最小の文字列を求めよ O(|S|)。
- S+Sの辞書順最小の接尾辞を求めれば良い。
- 各iについて、T[i:]がS[1],..,S[k]のうち何個を接頭辞として持つか列挙せよ
- Tの接尾辞木に対して、S[1],S[2],..,S[k]に対応する頂点の部分木にそれぞれ１加える。和が接頭辞の個数に等しい。
- 各iについて、T[:i]がS[1],..,S[k]のうち何個を接尾辞として持つか列挙せよ
- reverseして接頭辞に帰着する。
- 全てのペア(i,j)について、S[i]+S[j]がTに何箇所部分文字列として含まれるかの総和を求めよ。（ECR070E）
- T[:i]に接尾辞として含まれるS[1],..,S[k]の個数をf(i), T[i+1:]に接頭辞として含まれるS[1],..,S[k]の個数をg(i+1)としてΣf(i)g(i+1)が求まれば良い。
- Sの接尾辞木をS+Tの接尾辞木に更新せよ。
- Ukkonenのアルゴリズム
- 各iについて、S[:i]が部分文字列としてTに何個含まれるか求めよ O(|S|)
- iの昇順に接尾辞木で探索すれば良い。S[:i+1]の探索にはS[:i]の探索を再利用する。
- Sの部分文字列の集合の要素のうち、辞書順でk番目のものを求めよ。
- 二分探索木とほぼ同様
- Sの部分文字列のうち、辞書順でTより大きい最小の部分文字列を答えよ。O(|S|)
- 二分探索木とほぼ同様
- Sの部分文字列のうち、uniqueな回分の個数を答えよ O(|S|)
- Sの部分文字列のうち、uniqueな回分の辞書順 k 番目のものを答えよ O(|S|)
Comments