（Compressed） Suffix Tree とは何かということと，その Suffix Array を用いた構築方法について説明します．

[1] Suffix Array と substring の関係

substring とは，suffix の prefix とのことだと言い換えられます．

suffix array を求めて，これを suffix の列だと思いましょう．次の図では，右側に suffix を書き並べています．

右側に書いた suffix のひとつひとつの文字がありますが，それを suffix のその文字までの prefix と対応させることで，ひとつひとつの文字が substring を表していると考えることができます．ただしこの時点では，出現位置の異なる同じ substring は別のものとして図示されています．

[2] Suffix Tree

[1] の図において，上下の \(2\) マスであって同じ substring であるものをまとめてみます．どの \(2\) マスをまとめるかという情報は lcp table が持っています．

このようにすると出現位置のみ異なる substring がまとまって，長方形（横幅が \(1\)）ひとつずつが相異なる substring に対応します．例えば空でない substring の種類数は，[1] の図から [2] の図を得るまでに何か所でマスがマージされるかを考えると，\(\frac{N(N+1)}{2}-\mathrm{sum(lcp)}\) であることなども分かります（問題）．

ある substring の prefix であるような substring はひとつ左に進んだ長方形に対応する substring です．この長方形を親として根付き木を作ると，substring 全体および，その末尾への \(1\) 文字追加・削除の関係を根付き木として表すことができます．これが Suffix Tree です．

これは suffix 全体から Trie を作ったものと見なすこともできます．Trie では，文字は頂点ではなく辺に割り当てられると考えることも多いと思いますが，上の図では頂点に文字を割り当てる形で図示しています．

[3] Compressed Suffix Tree

さらにここから，縦幅の等しい親子をまとめます．（別の言い方としては，Trie を Patricia Trie として圧縮します．）これは Compressed Suffix Tree と呼ばれます．

縦幅 \(h\)，横幅 \(w\) の長方形は，出現回数が \(h\) であるような substring \(w\) 個を表していることになります．

このような木を作る利点は，木の大きさにあります．[2] の suffix tree では，木の頂点を substring の種類に対応させたために，根以外の頂点の個数が最大で \(\frac{1}{2}N(N+1)\) 個あります．

一方 [3] の木は根以外の頂点の個数は高々 \(2N-1\) 個です．木を子方向に進む過程が，「縦幅 \(N\) の区間を分割する」という操作の反復だと見なせるからです．頂点に対応する substring を \(S[i,j_1],\ldots, S[i,j_2]\) であるとき頂点の情報を \(3\) つ組 \((i,j_1,j_2)\) などとして表現することにすると，Compressed Suffix Tree は \(O(N)\) の大きさのデータによって表すことができます．

この木を構築するには，区間 \([0,N)\) を lcp が最も小さい場所で分割していくことを再帰的に行えばよいです．Suffix Array と lcp table は手に入れてある前提で，セグメント木などを用いると \(O(N\log N)\) 時間，単調スタックを用いると \(O(N)\) 時間でできます．

[4] 本問の解法

ゲームの手は，[2] の木で，子をひとつ選び進むことだと見なせます．あとはこの解法を [3] の木で \(O(N)\) 時間で行うことを考えればよいです．

実装方針のひとつは明示的に木を作ってしまうことです．他には，明示的に木を作らないまま suffix tree に関する dfs を実装するということも考えられます．例えば dfs(l, r, k)：suffix array の \(l\) 番目の要素から \(r\) 番目の要素までの部分，長さ \(k\) 以上の suffix が対象．というような再帰関数を実装して，\(l,r\) 間で lcp の最も小さい部分で区切り，再帰的な計算を行うようにすればよいです．