定数時間で LCS を求められる場合があるよ

入力長に対して線形時間 + 編集距離に対して二乗時間で LCS を求めるよ - えびちゃんの日記

編集距離が 0 の場合は定数時間で LCS を求められます。

文字列の長さが LCS です。

ここでは文字列の長さを定数時間で求められることを仮定しましたが、求められない場合は文字列の長さに対して線形時間かもしれません。