Challenge: Longest Common Subsequence

Lab Java Advanced 30 points

Read two words and print the length of their longest common subsequence (letters in the same order, not necessarily side by side).

Input

Two words, one per line (up to 1000 letters each).

Output

The LCS length.

Example

Input

abcde
ace

Output

Sample input available Sample output available

Editor

Java

Hints

dp[i][j] = LCS of the first i letters of a and first j letters of b.

Match: dp[i-1][j-1] + 1. No match: the bigger of dp[i-1][j] and dp[i][j-1].

Solution explanation

O(|a| × |b|) time and memory. Trying all subsequences would be O(2ⁿ).

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(), b = sc.next();
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(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]);
            }
        }
        System.out.println(dp[a.length()][b.length()]);
    }
}

Output

Answer