Under construction

Still being built. Things may change

LCS 6

Time limit1sMemory limit8 MB

Summary
Given two uppercase strings of up to 50000 characters, print the length of their longest common subsequence.
Level

Hard8 of 10

Topics
String, Dynamic programming, Binary search
Solved
No attempts yet

Problem

The LCS (Longest Common Subsequence) problem asks, given two sequences, for the longest sequence that is a subsequence of both.

For example, the LCS of ACAYKP and CAPCAK is ACAK.

Input

The first and second lines give two strings. Each string consists only of uppercase letters and is at most 50000 characters long.

Output

Print the length of the LCS of the two strings given as input on the first line.

Examples2

  1. Example 1

    Input
    ACAYKP
CAPCAK
    Expected output
    4

  2. Example 2

    Input
    WEDONTNEEDNOEDUCATION
WEDONTNEEDNOTHOUGHTCONTROL
    Expected output
    16