Two strings A and B made of lowercase English letters are given.
A subsequence of a string is what remains after deleting some of its letters (possibly none) and joining the rest in their original order.
The remaining letters do not have to be next to each other.
For example, "ace" is a subsequence of "abcde", but "aec" is not.
Print the length of the longest string that is a subsequence of both A and B.
If the two strings share no letter, print 0.
Input
The first line is A and the second line is B. Both consist only of lowercase English letters (a–z), and each has length from 1 to 1,000.
Output
One number: the length of the longest common subsequence
Example 1 · stdin
abcbdab
bdcaba
stdout
4
Example 2 · stdin
abc
def
stdout
0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Let L[i][j] be the answer for the first i letters of A and the first j letters of B: when the two letters match it is L[i-1][j-1] + 1, otherwise max(L[i-1][j], L[i][j-1]) (dynamic programming). The table is 1,001 × 1,001, about a million cells, so C, C++, Java, C#, Python, JavaScript and TypeScript can build it in 2D, but one Craykon list holds at most 10,000 items, so it would have to be split into 1,001 inner lists of 1,001 cells. Only the row above is used, so shrinking to one row (length of B + 1 cells) is cleaner. The trap there: the left cell row[j - 1] already holds this row's value, so the upper-left (diagonal) cell must be saved in a diag variable before it is overwritten — without it, "aa" and "aaaa" give 4. Also, a subsequence may skip letters, so it differs from the longest common contiguous substring (2 for "abxcd" and "abycd"; the answer is 4). Greedily matching the next equal letter from the front is wrong too (for "zabcd" and "abcdz", grabbing z first gives 1; the answer is 4). Comparing one letter: in Python, JavaScript and TypeScript b[j - 1] is a length-1 string, Java needs b.charAt(j - 1) (no [] on strings), in C#, C and C++ b[j - 1] is a char, and in Craykon b[j - 1] is a one-letter string and foreach (ch in a) walks the letters. When reading lines, use strip()/trim()/Trim() so a trailing \r or space does not become a letter (C and C++ scanf("%s")/cin >> skip it on their own).
Pythonmain.py · 16 lines
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])
JavaScriptmain.js · 14 lines
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]);
TypeScriptmain.ts · 16 lines
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]);
JavaMain.java · 25 lines
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]); }}
C#Main.cs · 25 lines
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]); }}
C++main.cpp · 22 lines
#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";}
Cmain.c · 22 lines
#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;}
Craykonmain.cray · 25 lines
a = Console.ReadLine().Trim();b = Console.ReadLine().Trim();m = b.Length;// row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이// 1,001 × 1,001 표 대신 한 줄(m + 1칸)만 둔다row = NewList(m + 1, 0);foreach (ch in a){ diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (j = 1; j <= m; j++) { up = row[j]; if (ch == b[j - 1]) { row[j] = diag + 1; } else { row[j] = Mathf.Max(row[j], row[j - 1]); } diag = up; }}Console.WriteLine(row[m]);