この問題は各タイプ2のクエリにおいて、\(T_x\) と \(T_y\)の最長共通接頭辞の長さを求めることで解くことができます。

最長共通接頭辞の長さが求まった後は、以下のように場合分けを行います。

最長共通接頭辞の長さを\(X\)とします。

• \( |T_x| = |T_y| = X\)のとき

  \(T_x\) と \(T_y\) は同じ文字列です。=を出力します。

• \( |T_x| \neq |T_y| = X\)のとき

  \(T_y\)は\(T_x\)の接頭辞かつ\(T_x \neq T_y\)なので、辞書順で\(T_x > T_y\)です。

• \( |T_y| \neq |T_x| = X\)のとき

  \(T_x\)は\(T_y\)の接頭辞かつ\(T_x \neq T_y\)なので、辞書順で\(T_x < T_y\)です。

• 上記以外のとき

  文字列\(T_x\)と\(T_y\)の\(X+1\)番目を辞書順で比較した結果が\(T_x\)と\(T_y\)を辞書順で比較した結果と一致します。
  文字列 \(T_x,T_y\) の \(X+1\)番目は、各文字列に対して追加された \(S\) の部分文字列の区間の配列と、区間の長さの累積和をもっておくことで二分探索を用いて\(O(\log Q)\)で取得できます。

よってこの問題は \(T_x\) と \(T_y\) の最長共通接頭辞の長さを高速に求めることができれば解くことができます。

ローリングハッシュを用いる方法

\(T_x\) と \(T_y\) の \(k\) 文字目までのハッシュを取得し一致判定ができれば、先頭から一致している文字列の長さで二分探索をすることで最長共通接頭辞の長さを求めることができます。

よって、各文字列 \(T_i\) の先頭 \(k\) 文字のハッシュが高速に取得できれば良いです。

まず、\(O(N)\) かけて \(S\) の部分列のハッシュ値を \(O(1)\) で求められるようにしておきます。ハッシュにはローリングハッシュを用いることで、ハッシュ同士の結合ができるようにします。

各文字列 \(T_i\) に対して、各追加クエリが行われた時点での以下の情報を記録します。

• 累積文字数 : 文字列を追加した後の \(T_i\) の全体の長さ
• 累積ハッシュ値 : 文字列を追加した後の \(T_i\) 全体のハッシュ値
• 追加された区間の情報 : 追加クエリで \(S\) のどの区間が追加されたか

記録すべき値は、そこまでの累積文字数や累積ハッシュ値から \(O(1)\) や \(O(\log (NQ))\) で求めることができます。この3つの情報を各文字列に対して、配列で管理しておきます。

\(T_i\) の先頭 \(k\) 文字のハッシュを取得することを考えます。

1. \(T_i\) の \(k\) 文字目が \(T_i\) に対する何番目の追加クエリで追加されたものなのかを計算します。これは、累積文字数の配列に対して二分探索を行うことで \(\mathrm{O}(\log Q)\) で求めることができます。ここで求めた値を \(q\) とします。
2. \(q-1\) 回追加クエリを行った時点の文字列 \(T_i\) のハッシュを取得します。これは累積ハッシュ値の配列の値を参照することで \(\mathrm{O}(1)\) で取得できます。
3. \(q\) 回目の追加クエリで追加された文字列の内、先頭から文字列 \(T_i\) の \(k\) 番目にあたる部分までのハッシュ値を求めます。これは、\(q-1\) 回目までの累積文字数を \(X\)、\(q\) 回目で追加された文字列 \(S\) の区間を \([l_q,r_q]\) とすると文字列 \(S\) に対して \([l_{q} ,l_{q} + k - X)\) の部分文字列に対するハッシュ値を求めればよいです。
4. 手順2と手順3で得られたハッシュ値をその順で結合します。この結果が \(T_i\) の先頭 \(k\) 文字のハッシュと一致します。

上記の手順によって、\(\mathrm{O}(\log Q)\) で \(T_i\) の先頭 \(k\) 文字目までのハッシュを取得することができました。よって、\(\mathrm{O}(\log {(\min(|T_x|,|T_y|))} \log Q)\) で \(T_x\) と \(T_y\) の最小共通接頭辞の長さを求めることができました。

文字列の長さは最大で\(4 \times 10^{10}\) になるため、ハッシュの衝突に注意が必要です。

SA+LCP+RMQを使う方法

文字列 \(S\) に対して、Suffix Array , LCP Arrayを構築し、LCP Arrayに対してSparse Tableを用いることで区間minクエリを \(O(1) \) でできるようにすると、文字列 \(S\) の部分列同士の最長共通接頭辞の長さが \(O(1)\)で取得できます。

上記を使うことで、文字列 \(S\) の部分列の結合によって作られた文字列 \(X , Y\) の比較が\(O(|X| + |Y|)\) (ただし、\(|X|\)は文字列 \(X\)が何個の文字列 \(S\) の区間から構築されたかを表すとします。) でできるようになります。

クエリを先読みし、タイプ1のクエリをすべて処理した後の文字列の列 \(T\) をソートすることを考えます。長さ \(N\) の配列のソートをするとき、各要素の比較回数が\(O((\log N)^2)\)で抑えられるようなソートを用いることで\(O(Q (\log |T|)^2)\) でソートができます。

ソートができた後は、ソート後の列 \(T\) に対して隣接する要素同士の最長共通接頭辞の長さを記録した配列を作成します。この配列に対して、Sparse Tableを用いて区間minクエリを行えるようにすることで、\(O(1)\)で最終状態における文字列 \(T_x\) と \(T_y\) の最長共通接頭辞の長さが取得できます。

クエリ先読みをしたタイプ2のクエリに対して、その時点における\(T_x\) と \(T_y\) の最長共通接頭辞の長さを求めたいです。これは、最終状態における\(T_x\) と \(T_y\) の最長共通接頭辞の長さと、クエリ時点の \(T_x , T_y\) の長さのminを取ることで求めることができます。