定義

LCSは、2つの文字列で順序を維持しながら共通する最長の部分列を見つけるアルゴリズムです。「部分列」は連続でなくても良く、元の順序だけ維持すれば良いです。

主な特性

• ✓文字一致時: dp[i][j] = dp[i-1][j-1] + 1
• ✓文字不一致時: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• ✓2Dテーブル使用: 各文字列を行/列に
• ✓逆追跡で実際のLCS文字列を復元可能

時間計算量