Trip
Time limit1sMemory limit128 MB
Given two strings, print all longest common subsequences in lexicographic order without duplicates.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Backtracking, String, Sorting
- Solved
- No attempts yet
Problem
Alice and Bob want to go on a trip together. Each of them has planned a route: an ordered list of cities to visit. A route may visit the same city more than once.
Because they want to travel together, they must agree on a single common route. Neither is willing to reorder the cities on their own route or to add new cities, so the only thing they may do is delete some cities. Naturally, the common route should be as long as possible.
The region has exactly 26 cities, encoded as the lowercase letters a to z. A common route is therefore a longest common subsequence (LCS) of the two given lists.
Input
The first line contains Alice's list and the second line contains Bob's list. Each list is a string of 1 to 80 lowercase letters (a-z) with no spaces.
Output
Print every longest common route, one per line, with no route repeated. Print the routes in lexicographically ascending order. It is guaranteed that at least one non-empty common route exists and that there are at most 1000 distinct ones.