英小文字からなる文字列 A と B が与えられる。
ある文字列から何文字か消して（一文字も消さなくてもよい）、残りの文字を元の順につないだものを、その文字列の部分列という。
残る文字は隣り合っていなくてもよい。
たとえば "ace" は "abcde" の部分列だが、"aec" はそうではない。
A の部分列であり B の部分列でもある文字列のうち、最も長いものの長さを出力せよ。
共通の文字が一つもなければ 0 を出力する。
abcbdab bdcaba
4
abc def
0
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
L[i][j] = A の先頭 i 文字と B の先頭 j 文字の答えとすると、二文字が同じなら L[i-1][j-1] + 1、違えば max(L[i-1][j], L[i][j-1]) です（動的計画法）。
表は 1,001 × 1,001 = 約 100 万マスなので C・C++・Java・C#・Python・JavaScript・TypeScript は二次元で作っても構いませんが、Craykon のリストは一つ 10,000 個までなので、外側 1,001 個に内側 1,001 マスずつ分ける必要があります。
すぐ上の行しか使わないので、一行（B の長さ + 1 マス）に縮めるのがすっきりします。
そのときの罠：左のマス row[j - 1] はもう今の行の値に変わっているので、上の行の左上（対角）のマスは上書きする前に diag 変数に取っておく必要があります — 取っておかないと "aa" と "aaaa" の答えが 4 になります。
また、部分列は飛ばしてよいので、連続した共通部分文字列（"abxcd"・"abycd" で 2）とは違います（答え 4）。
先頭から同じ文字をすぐ組にする貪欲法も間違いです（"zabcd"・"abcdz" で z を先に取ると 1、答え 4）。
一文字ずつの比較：Python・JavaScript・TypeScript は b[j - 1] が長さ 1 の文字列、Java は b.charAt(j - 1)（文字列に [] は使えません）、C#・C・C++ は b[j - 1] が char、Craykon も b[j - 1] が一文字の文字列で、それぞれ (ch の中 a) で文字を回ります。
行を読んだら末尾の \r や空白が文字に混ざらないよう strip()・trim()・空白除去() をします（C・C++ の scanf("%s")・cin >> は自然に飛ばします）。
a = input().strip()b = input().strip()m = len(b) # row[j] = (a의 지금까지 읽은 앞부분)과 b[:j]의 가장 긴 공통 부분 수열 길이. 2차원 표 대신 한 줄만 둔다row = [0] * (m + 1)for ch in a: diag = 0 # 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for j in range(1, m + 1): up = row[j] if ch == b[j - 1]: row[j] = diag + 1 elif row[j - 1] > row[j]: row[j] = row[j - 1] diag = upprint(row[m])const [a, b] = require("fs").readFileSync(0, "utf8").split("\n").map((s) => s.trim());const m = b.length; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다const row = new Array(m + 1).fill(0);for (const ch of a) { let diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (let j = 1; j <= m; j++) { const up = row[j]; row[j] = ch === b[j - 1] ? diag + 1 : Math.max(row[j], row[j - 1]); diag = up; }}console.log(row[m]);import { readFileSync } from "node:fs"; const [a, b]: string[] = readFileSync(0, "utf8").split("\n").map((s) => s.trim());const m: number = b.length; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다const row: number[] = new Array<number>(m + 1).fill(0);for (const ch of a) { let diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (let j = 1; j <= m; j++) { const up = row[j]; row[j] = ch === b[j - 1] ? diag + 1 : Math.max(row[j], row[j - 1]); diag = up; }}console.log(row[m]);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String a = in.readLine().trim(); String b = in.readLine().trim(); int m = b.length(); // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 int[] row = new int[m + 1]; for (int i = 0; i < a.length(); i++) { char ch = a.charAt(i); int diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (int j = 1; j <= m; j++) { int up = row[j]; row[j] = ch == b.charAt(j - 1) ? diag + 1 : Math.max(row[j], row[j - 1]); diag = up; } } System.out.println(row[m]); }}using System; class Program{ static void Main() { string a = Console.ReadLine().Trim(); string b = Console.ReadLine().Trim(); int m = b.Length; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 int[] row = new int[m + 1]; foreach (char ch in a) { int diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (int j = 1; j <= m; j++) { int up = row[j]; row[j] = ch == b[j - 1] ? diag + 1 : Math.Max(row[j], row[j - 1]); diag = up; } } Console.WriteLine(row[m]); }}#include <algorithm>#include <iostream>#include <string>#include <vector> int main() { std::string a, b; std::cin >> a >> b; int m = static_cast<int>(b.size()); // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 std::vector<int> row(m + 1, 0); for (char ch : a) { int diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (int j = 1; j <= m; j++) { int up = row[j]; row[j] = ch == b[j - 1] ? diag + 1 : std::max(row[j], row[j - 1]); diag = up; } } std::cout << row[m] << "\n";}#include <stdio.h>#include <string.h> int main(void) { static char a[1002], b[1002]; scanf("%1001s %1001s", a, b); int n = (int)strlen(a), m = (int)strlen(b); /* row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 */ static int row[1001]; for (int i = 0; i < n; i++) { int diag = 0; /* 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 */ for (int j = 1; j <= m; j++) { int up = row[j]; if (a[i] == b[j - 1]) row[j] = diag + 1; else if (row[j - 1] > row[j]) row[j] = row[j - 1]; diag = up; } } printf("%d\n", row[m]); return 0;}a = コンソール.行読み().空白除去();b = コンソール.行読み().空白除去();m = b.長さ; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이// 1,001 × 1,001 표 대신 한 줄(m + 1칸)만 둔다row = 新リスト(m + 1, 0);それぞれ (ch の中 a){ diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 繰り返す (j = 1; j <= m; j++) { up = row[j]; もし (ch == b[j - 1]) { row[j] = diag + 1; } でなければ { row[j] = 数学.大きい方(row[j], row[j - 1]); } diag = up; }}コンソール.書く(row[m]);