LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDEInteractive TasksOutput-Only Tasks
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion FindSqrt Decomposition
Combinatorics
Addition PrincipleMultiplication PrincipleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsVectorsCross and Dot ProductLinesPolygonsAnglesPoint in PolygonDistances and Intersection PointsConvex HullCircles
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPDP problemsTree DPBitmask DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

Longest Common Subsequence (LCS)

EasyProblem #5
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

A classic 2D DP problem. Try to define what dp[i][j] should mean before writing any code.

Given two strings, find the length of the longest common subsequence between them.

A subsequence is a sequence of characters obtained by deleting zero or more characters from a string, without changing the order of the remaining characters (the characters don't have to be next to each other). A common subsequence of two strings is a subsequence that appears in both of them.

Input

First line of input will be the string s1​.
In the second line will be the string s2​.

Output

A single number - the length of the longest common subsequence of s1​ and s2​.

Example

Input
abcde
ace
Output
3

The longest common subsequence is ace, with a length of 3.

Constraints

1≤∣s1​∣,∣s2​∣≤1000

Both strings consist of lowercase English letters.

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit