Finds Longest Common Subsequence of given two Strings
The Longest Common Subsequence (LCS) - Dynamic Programming
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. The Longest common subsequence (LCS) of two sequences is a subsequence, with maximal length, which is common to both the sequences.
Given two strings, A = a1a2...an and B = b1b2...bm, find the longest common subsequence and print it. If there are multiple common subsequences with the same maximum length, print all of them.
Input Format Two strings A and B given in two lines.
Constraints The characters of strings are English lowercase alphabetic letters. 0 <= length(A), length(B) <= 100
Output Format Print the longest common subsequence on one line. In case of multiple valid answers, print all of them one subsequence per line.
Sample Input president providence
Sample Output priden