\(T\) を連長圧縮したときの先頭の文字の位置のみに着目します。これらを \((X_i)\) とします。連長圧縮の長さを \(M\) としたとき、\((X_i)\) は長さ \(M\) の列ですが、便宜上 \(X_{M + 1} = N + 1\) とします。

\(T_{X_i}\) に対応する \(S_{Y_i}\) を考えます。このとき \(Y_i\) が満たすべき条件は以下の通りです。

• \(Y_1 < Y_2 < ... < Y_M\)
• \(Y_i \le X_i\)
• \(S_{Y_i} = T_{X_i}\)

条件を満たすような \(Y_i\) は、明らかに大きいほど最終的に \(T\) を作成するにあたって有利なので、右から貪欲に取るとしてよいです。これは、各位置についてそれより左側にある文字 \(c\) のうち最も右側の位置を左から順に計算しておくことで \(O(N \sigma)\) で \((Y_i)\) が求まります。 再度便宜上 \(Y_{M + 1} = N + 1\) とします。

ここから、すべての \(Y_i\) を \(X_i\) に一致させるまでにかかる手数を計算します。 \(Y_i\) を先頭とした同じ文字が連続した位置の右端を \(R_i\) とします。各ステップにおいて、\(R_i\) は \(X_{i + 1}\) 未満の範囲でなるべく伸ばすのが最適です。 このとき、すべての \(i\) について \(R_i = X_{i + 1} - 1\) となるまでの手数が答えです。

ところで、 (\(R_i = X_{i + 1} - 1\) となるまでの手数) \(=\) (\(R_{i + 1} \ge X_{i + 1} - 1 + 1\) となるまでの手数) \(=\) (\(R_{i + 2} \ge X_{i + 1} - 1 + 2\) となるまでの手数) \(= \ldots\) です。あるタイミングで、\(Y_j \ge X_{j} + (j - i) - 1\) となります。(少なくとも \(j = M + 1\) が条件を満たす)

初期値で条件を満たしているとき、\(R_j \ge X_{i + 1} + (j - i) - 1\) となるまでの手数は明らかに \(0\) です。

よって、\(Y_j - j\) を管理した segment tree 上で \(Y_j - j \ge X_{i + 1} - i - 1\) を満たす最小の \(j\) を求めればよいです。

計算量は \(O(N \log N)\)