Hide

Problem G
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

Please log in to submit a solution to this problem

Log in