元の問題の部分問題として登場する次の問題について解説します。

問題1：長さ \(N\) の文字列 \(S\) と、\(K\) 個の区間 \([L_i,R_l]\) が与えられる。与えられた区間たちを、対応する部分文字列の辞書順にソートせよ

また、似て非なる問題として次の問題もついでに考えます。

問題2：長さが \(N\) 以下の文字列が \(K\) 個与えられる。辞書順にソートせよ

愚直解法

組み込みのソート関数などを用いソートします。文字列の比較に \(O(N)\) かかるため、問題1、問題2ともに計算量 \(O(NK\log K)\) で解くことができます。

trie

公式解説にかかれている解法です。与えられた文字列全てを持つ trie を構築してから DFS することで、各文字列が辞書順で何番目か求めることができます。長さ \(O(N)\) の文字列を trie に挿入するには \(O(N)\) かかりますが、ある文字列を trie に挿入するとそのprefix を全て持つことになるので、問題1の場合は(全ての部分文字列ではなく)全ての suffix を挿入すればよく、計算量は \(O(N^2)\) になります。そのような性質のない問題2の計算量は \(O(NK)\) となります。

Rolling hash

Rolling hash を適切に用いると、\(2\) つの文字列の大小比較が \(O(\log N)\) でできます（LCP の長さを二分探索）。この比較方法を用いてソートを行うことで、愚直な比較によるソートより高速に解くことができます。事前にRolling hashを計算するのにかかる時間を含めると、問題1は \(O(N+K\log K \log N)\)、問題2は \((NK+K\log K\log N)\) で解くことができます。

参考文献：週刊 spaghetti_source

LCP Array+RMQ

LCP Array を構築し、クエリ \(O(1)\) で static RMQ に答えることができるデータ構造(sparse table など)と組み合わせることで、\(2\) つの文字列の LCP の長さを \(O(1)\) で求めることができます。これを用いると文字列の大小比較が \(O(1)\) ででき、問題1を\(O(N\log N+K\log K)\) で解けます。問題2をこの方法で効率よく解くのは困難です。