【競プロ】LCS（最長共通部分列問題）の解説とWebフロントエンドでの応用

先月、AtCoderでようやく緑上位に食い込むことができました。

水色まではまだまだ遠い・・。

さて、最近フロントエンドのコーディング業務で LCS 問題 を取り扱う場面がありました。 「競技プログラミングは業務にほとんど関係ない」とずっと思っているので、興奮と感動、および汗が止まりませんでした。

こんなの記事にするしかないな～と思ったので、解説いたします。良かったら読んであげてください。

目次

1. ▸LCSとは？
2. ▸問題文（AtCoder F - LCS）
3. ▸アルゴリズムの考え方
4. ▸C++ 実装と解説
5. ▸計算量
6. ▸入出力例の確認
7. ▸Webフロントエンドでの応用

---

LCSとは？

LCS（Longest Common Subsequence / 最長共通部分列） は、2 つの文字列に共通して存在する部分列のうち、最も長いものを求める超有名な古典アルゴリズムです。

部分列（Subsequence） とは、元の文字列から 0 個以上の文字を（連続じゃなくてもOK）取り除き、残りを順序そのままつなげた文字列のこと
部分文字列（Substring）との違い：部分文字列は連続した文字じゃないとダメですが、部分列は飛び飛びでも大丈夫です。ここを混同しがちなので注意

---

問題文（AtCoder F - LCS）

実行時間制限: 2 sec / メモリ制限: 1024 MiB / 配点: 100 点

文字列 s および t が与えられます。
s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。
制約
• s および t は英小文字からなる文字列
• 1 ≤ |s|, |t| ≤ 3000

入出力例

---

バカめ！こんなの簡単だろ！

「全パターン試せばいいじゃん！」と思うのが最初の発想ですよね。

たとえば s のすべての部分列を列挙して、それが t の部分列でもあるか確認する、という全探索アプローチです。

// NG 例：全探索（TLE になる）// s のすべての部分列を列挙するfor(int bit=0; bit<(1<< n); bit++){    string sub="";for(int i=0; i< n; i++){if(bit&(1<< i)) sub+= s[i];}// sub が t の部分列かどうかチェック…}

一見シンプルでわかりやすいですが、s の部分列の数は最大 2^|s| 個！

|s| = 3000 のとき → 2^3000 通り ≈ 10^900 通り

これは宇宙の原子の数（約 10^80）をはるかに超えます^_^

どう頑張っても無理ということです。

再帰で書いても同じ問題

「じゃあ再帰で LCS の長さを求めよう」と素直に実装するとこうなります。

// NG 例：メモ化なし再帰（TLE になる）intlcs(string& s, string& t,int i,int j){if(i==0|| j==0)return0;if(s[i-1]== t[j-1])returnlcs(s, t, i-1, j-1)+1;returnmax(lcs(s, t, i-1, j),lcs(s, t, i, j-1));}

これの計算量は最悪 O(2^(|s|+|t|)) で、同じく爆発します（笑）同じ (i, j) の組み合わせを何度も再計算してしまうのが原因です。

「同じ部分問題が何度も登場する」＝ 動的計画法（DP）を使うことができます。

---

アルゴリズムの考え方

Step 1 ― DP テーブルで長さを求める

dp[i][j] を「s の先頭 i 文字と t の先頭 j 文字の LCS の長さ」と定義します。

漸化式はこれだけ！

s[i-1] == t[j-1] のとき:  dp[i][j] = dp[i-1][j-1] + 1それ以外:                  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

「文字が一致したら斜め上から +1、不一致なら上か左の大きい方を引き継ぐ」とイメージすると掴みやすいです。

Step 2 ― バックトラックで実際の文字列を復元する

DP テーブルを右下 (|s|, |t|) から左上 (0, 0) へ逆向きにたどります。

s[i-1] == t[j-1] なら → その文字を採用して i--, j--dp[i-1][j] >= dp[i][j-1] なら → i--（s 側を巻き戻す）
それ以外 → j--（t 側を巻き戻す）

逆順に文字を追加しているので、最後に文字列を反転させれば完成です！

DP テーブルのイメージ（例 1）

s = axyb, t = abyxb
     ""  a  b  y  x  b
 ""   0  0  0  0  0  0
  a   0  1  1  1  1  1
  x   0  1  1  1  2  2
  y   0  1  1  2  2  2
  b   0  1  2  2  2  3   ← LCS の長さは 3

バックトラック:

(4,5)→(3,4)→(2,3)→(1,1)→(0,0)

採用文字:

b → x → a

→ 反転して

axb

ということです。かんたんですね。

---

C++ 実装と解説

#include<bits/stdc++.h>usingnamespace std;
intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);
    string s, t;    cin>> s>> t;
int n= s.size(), m= t.size();
// Step 1: DP テーブル構築// dp[i][j] = s[0..i-1] と t[0..j-1] の LCS 長    vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int i=1; i<= n; i++){for(int j=1; j<= m; j++){if(s[i-1]== t[j-1]){                dp[i][j]= dp[i-1][j-1]+1;}else{                dp[i][j]=max(dp[i-1][j], dp[i][j-1]);}}}
// Step 2: バックトラックで LCS を復元    string result="";int i= n, j= m;
while(i>0&& j>0){if(s[i-1]== t[j-1]){            result+= s[i-1];// 共通文字を採用            i--;            j--;}elseif(dp[i-1][j]>= dp[i][j-1]){            i--;// s 側を巻き戻す}else{            j--;// t 側を巻き戻す}}
// 逆順に追加したので反転reverse(result.begin(), result.end());
    cout<< result<<"\n";return0;}

コードのポイント

---

計算量

制約 |s|, |t| ≤ 3000 なら最大 3000 × 3000 = 900 万回 の操作で、2 秒以内に余裕で収まります。

空間最適化のヒント：LCS の「長さだけ」を求めるなら、1 行前だけ保持する 1 次元 DP（O(min(|s|, |t|)) 空間）に削減できます。ただし復元が必要な今回は 2 次元テーブルが必要です。

---

入出力例の確認

例 4（abracadabra vs avadakedavra）

s = abracadabra  (長さ 11)t = avadakedavra (長さ 12)

LCS 長 = 7
出力例: aaadara

aaadara が abracadabra と avadakedavra 両方の部分列になっていることを手元で追いかけてみると理解が深まります！

---

Webフロントエンドでの応用

LCS は競プロだけじゃなく、フロントエンド開発の身近なところでめちゃくちゃ使われています。

1. 差分検出（Diff）― Virtual DOM / テキストエディタ

React などの Virtual DOM は新旧ノードリストの差分を効率よく計算するために LCS ベースのアルゴリズムを使っています。また

git diff

や Monaco Editor（VS Code の中核エディタ）のインライン差分表示も LCS が土台です。

// 簡易 LCS を使ったテキスト差分の例（JavaScript）functionlcsLength(a, b){const dp=Array.from({length: a.length+1},()=>newArray(b.length+1).fill(0));for(let i=1; i<= a.length; i++){for(let j=1; j<= b.length; j++){if(a[i-1]=== b[j-1]) dp[i][j]= dp[i-1][j-1]+1;else dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);}}return dp[a.length][b.length];}
// 変更前後のコード行を配列として渡すconst oldLines=["const x = 1;","let y = 2;","return x + y;"];const newLines=["const x = 1;","const z = 3;","return x + z;"];console.log(lcsLength(oldLines, newLines));// 1（"const x = 1;" のみ共通）

2. あいまい検索・スペルサジェスト

検索フィールドでユーザーの入力と候補文字列の「共通部分の長さ」を LCS でスコアリングすると、より直感的なサジェストが作れます。編集距離（レーベンシュタイン距離）と組み合わせると精度がさらに上がります！

// LCS スコアを使った検索候補ランキングfunctionlcsScore(query, candidate){// LCS 長 / 候補文字列長 でスコア化（0〜1）returnlcsLength(query, candidate)/ candidate.length;}
const query="recat";// タイポconst candidates=["React","redux","recoil","relay"];const ranked= candidates.map(c=>({name: c,score:lcsScore(query.toLowerCase(), c.toLowerCase())})).sort((a, b)=> b.score- a.score);
console.log(ranked);// → [{ name: 'React', score: 0.8 }, ...]

3. コードレビューUI（GitHub / GitLab スタイル）

GitHub / GitLab のコードレビュー画面では変更前後のファイルを行単位で LCS にかけて、「削除行（赤）」「追加行（緑）」「変更なし行（白）」を判定しています。

4. JSON パッチ・状態管理の最適化

Redux などでリスト型ステートの差分パッチを生成するとき、LCS を使って最小変更操作（追加・削除）を計算することで不要な再レンダリングを防げます。

まとめ表

---

まとめ

• ▸LCS は 2 次元 DP で長さを求め、バックトラック で文字列を復元する
• ▸計算量は O(nm)（n, m は各文字列の長さ）で、制約 3000 × 3000 でも余裕
• ▸競プロだけじゃなく、差分検出・検索・UI の最適化 などフロントエンド開発でも超重要なアルゴリズム

LCS を理解すると、エディタの diff 表示や Virtual DOM の仕組みが「あ、これ LCS じゃん！」って見えてきます。ぜひ手を動かして実装してみてください！それではまた。