#10262 - Suffidromes

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Try all reversed prefixes of each string as possible suffixes, in order of increasing length, and lexicographic earliness. So, for the input:


Try "", "a", "w", "ew", "na", "dna", "sew", etc.

For each suffix, try appending it to both strings. If it turns only one into a palindrome, then that's your answer.

If at the end you find no solution, there's one more step to try. We may have a case like:

<blank line>

In this case, the solution is "b". Or we might have:


In this case, "ba" is the correct suffix.

Let S1 be the smaller string, and S2 be the larger string. If both are the same length, then it doesn't matter which you pick. Try 26 more suffixes, "a"+rev(S1) through "z"+rev(S1), where rev(S1) is S1 reversed.

If there are still no solutions after this step, then print "No solution."

Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site