# SPOJ TRIP

Jump to navigation Jump to search

## Summary

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

## Explanation

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

## Gotcha's

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

## Input

The first line of input contains a number ${\displaystyle T\leq 10}$ 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

Output all of the longest common subsequences in lexicographical order.

ababa
abaca
abcba
acaba
acaca
acbaa
acbca