SPOJ TRIP

From Algorithmist
Jump to navigation Jump to search

33 - TRIP - Trip[edit]

Summary[edit]

Given 2 strings of lower case letters find all the longest common subsequences.


Explanation[edit]

For more information about finding LCS see: http://www.algorithmist.com/index.php/Longest_Common_Subsequence

Gotcha's[edit]

For finding all of the longest common subsequences you should use a recursive function instead of an array which keeps the path.

Input[edit]

The first line of input contains a number that indicates the number of test cases to follow.Each test case consists of two lines; indicating the strings of at most size 80.

1
abcabcaa
acbacba


Output[edit]

Output all of the longest common subsequences in lexicographical order.

ababa
abaca
abcba
acaba
acaca
acbaa
acbca