给出由英文小写字母组成的字符串 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) 逐字遍历。
读行后要 strip()、trim()、去空白()，免得行尾的 \r 或空格混进字母里（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]);