Problem D
Palindrome Substring
A palindrome is a word or phrase that reads the same backwards or forwards. For this problem, we’re going to find all the different palindromes that occur inside a string.
We’ll say that string $a$ is a nontrivial palindrome substring of $b$ if $a$ is a substring of $b$, the sequence of characters in $a$ reads the same forwards or backwards, and $a$ is at least two characters long. Here, a substring of $b = b_1 b_2 \ldots b_ n$ is any string $b_ i b_{i+1} \ldots b_{i+j}$ where $i \geq 1$ and $j \geq 1$ and $i + j \leq n$.
Input
Input consists of up to $100$ lines. Each line contains a string of $1$ to $1000$ characters chosen from a–z. Input ends at end of file.
Output
For each input string, print out the list of all of its non-trivial palindrome substrings. Each list of palindromes should be sorted lexicographically, and should not contain duplicates. Print a blank line after the output for each input string.
| Sample Input 1 | Sample Output 1 |
|---|---|
thisisatest xxxxoooo |
isi sis oo ooo oooo xx xxx xxxx |
