Strings — Shortest Palindrome

solve(s) — you may add characters only in front of s. Return the shortest
palindrome you can build that way.

The characters you must add are the reverse of whatever follows the **longest palindromic
prefix** of s. Finding that prefix in O(n) is a KMP trick: build t = s + "#" + reverse(s)
and compute its failure table. The last value of the table is the length of the longest prefix
of s that is also a suffix of reverse(s) — in other words, the longest palindromic prefix of
s. The # separator stops matches from spilling across the two halves.

Examples

solve("aacecaaa")   → "aaacecaaa"
solve("abcd")       → "dcbabcd"
solve("abb")        → "bbabb"
solve("aba")        → "aba"