先頭から \(i\) 文字目までに含まれる A の文字数と B の文字数の差をキーにして \(i\) を値とする連想配列に入れておく.

\(j\) 文字目から始めて最長の長さを求めるためには, \(j\) 文字目までに含まれる A の文字数と B の文字数の差 \(S_j\) を計算し, 連想配列の中に \(-S_j\) をキーとするインデックスがあるかどうかを調べ, その最大値を求めればいい. (最大値しか使わないので, もともと連想配列には最大値だけを入れておけばいい)