記法

• アルファベットを \(\Sigma = \{\mathtt{a}, \mathtt{b}, \dots, \mathtt{z} \}\) とおき、その要素数を \(\sigma = \#\Sigma\) とします。
• 文字列 \(S\) の \(i\) 文字目以降の部分文字列を \(S[i\!:]\) と表記します。

解法

まず、以下に定義する \(\mathrm{len}, \mathrm{cnt}\) を求めましょう。

\[ \mathrm{len}[i][j] = \mathrm{LCS}(S[i\!:], T[j\!:]) \]

\[ \mathrm{cnt}[i][j] = \left(S[i\!:], \ T[j\!:] \text{ の LCS の種類数 } \right) \]

\(\mathrm{len}\) は後ろから DP することで \(O(NM)\) 時間で求めることができます。

次に \(\mathrm{cnt}\) を求めるために、以下の \(r_S, r_T\) を計算します。これは \(O(\sigma NM)\) 時間で求めることができます。

\[ r_S[i][c] = \min \{ i \lt k \mid (S[k] = c) \lor (k = N + 1) \} \\ \]

\[ r_T[j][c] = \min \{ j \lt k \mid (T[k] = c) \lor (k = M + 1) \} \]

すると \(\mathrm{cnt}\) も次のように \(O(\sigma NM)\) 時間で求めることができます。 なぜなら先頭の文字が \(c\) である任意の LCS は、位置 \(r_S[i][c], \ r_T[j][c]\) を先頭とするものに置き換えることができるからです。

\[ \displaystyle \mathrm{cnt}[i][j] = \sum_{c \in \Sigma_{i,j}} \mathrm{cnt}[r_S[i][c]+1][r_T[j][c]+1] \]

ここで、

\[ \Sigma_{i,j} = \left \{ c \in \Sigma \\ \ \middle| \ \begin{array}{l} r_S[i][c]\lt N,\ r_T[j][c]\lt M, \\ \mathrm{len}[i][j] = \mathrm{len}[r_S[i][c]+1][r_T[j][c]+1]+1 \end{array} \right \} \]

なお、\(\mathrm{cnt}\) の値は非常に大きくなる可能性があるため、素直に実装するとオーバーフローのおそれがあります。 しかし、\(k_i \leq 10^9\) であることから、適当な定数で打ち止めして問題ありません。

以上の結果を用いて、辞書順で \(k\) 番目の LCS を求めましょう。 \(S,T\) の LCS の長さを \(L (=\mathrm{len}[1][1])\) とします。 添え字のペア \((i,j) = (1,1)\) からスタートして、 \(l=1,2,\dots,L\) の順に文字を決定していきます。1文字目と2文字目以降で処理が変わる点に注意です。

• 1文字目 \((l=1)\)

  • 各文字 \(c\) について, \(\mathrm{len}[1][1] = \mathrm{len}[r_S[1][c]][r_T[1][c]]\) を満たすものがあれば, \(1\) 文字目が \(c\) となる LCS が存在する。
  • \(k \leq \mathrm{cnt}[r_S[1][c]][r_T[1][c]]\) であれば、求める LCS の \(1\) 文字目は \(c\) であるため, \(i = r_S[1][c], j = r_T[1][c]\) として、次の文字に遷移する。
  • そうでなければ \(k\) から \(\mathrm{cnt}[r_S[1][c]][r_T[1][c]]\) を引いて、辞書順で次の文字 \(c\) について調べる。

• 2文字目以降 \((l\geq 2)\)

  • 各文字 \(c\) について, \(\mathrm{len}[i][j] = \mathrm{len}[r_S[i+1][c]][r_T[j+1][c]]+1\) を満たすものがあれば, \(l\) 文字目が \(c\) となる LCS が存在する。
  • \(k \leq \mathrm{cnt}[r_S[i+1][c]][r_T[j+1][c]]\) であれば、求める LCS の \(l\) 文字目は \(c\) であるため, \(i = r_S[i+1][c], j = r_T[j+1][c]\) として、次の文字に遷移する。
  • そうでなければ \(k\) から \(\mathrm{cnt}[r_S[i+1][c]][r_T[j+1][c]]\) を引いて、辞書順で次の文字 \(c\) について調べる。

なお、 LCS の長さが \(0\) 、または \(k\) が LCS の種類数( \(=\mathrm{cnt}[1][1]\) )を超える場合は -1 となります。

この計算量は \(O(\sigma L) = O(\sigma \min(N, M))\) であるため、クエリ全体は \(O(Q \sigma \min(N, M))\) で求められます。

よってこの問題は \(O(\sigma NM + Q \sigma \min(N, M))\) で解くことができました。

クレジット

原案： mono_1729

解法： mono_1729, hirakuuuu, nu50218

問題準備・解説： US_cube

レビュー： akua

テスター： QCFium

校正： ngtkana