# SPOJ TRIP

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