214. Shortest Palindrome

题目

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

Credits:Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

解题思路

字符串匹配的KMP算法

见程序注释