LCS Problem in Linear Space
Solve Longest Common Subsequence Problem in Linear Space in Several Languages
Languages
- Ruby
- Crystal
- C++ (C++17)
- C#
Problem
Given two sequences X =〈x1, x2, … , xm〉and Y = 〈y1, y2, … , yn〉, find a longest common subsequence of X and Y.
Input
First line contains an integer T, representing the number of testcases. In the next T lines, each line contains two string X and Y.
- 2 ≤ T ≤ 20
- X and Y =~
/^[A-Za-z0-9]{5,1000}$/
Output
For each test case, output the LCS of X and Y on one line. If there exist more than one LCS, any one is acceptable. If the LCS doesn't exist, output a blank line.
Sample Input
2
ABACABAC CABCBAAB
lRk3W1I9WxwL8u3l2GA4 3In9qxKcLuN963Yxlvq4
Sample Output
ABAAB
3I9xLu3l4
Contributing
- Fork it ( https://github.com/c910335/LCS-Problem-in-Linear-Space/fork )
- Create your feature branch (git checkout -b add-new-language)
- Commit your changes (git commit -am 'add new language')
- Push to the branch (git push origin add-new-language)
- Create a new Pull Request
Contributors
- c910335 Tatsujin Chin - creator, maintainer
- david50407 David Kuo - C++17
- sharknevercries ZhengYuan Lee - C#