[LeetCode]Shortest Palindrome

实际上就是找从头开始的最长palindrome的长度，这样能让增添的字符数最少，从而让结果的palindrome最短。一般的方法是O(n^2)的时间，但是如果我们将s和reverse(s)连接，然后找出最长的公共前后缀p，那么p就是我们要求的最长从头开始的回文。当然人我们要在s和reverse(s)中间插入特殊字符来防止找到的p长度大于s的长度。求最长公共前后缀的方法就是KMP中求next数组的方法，具体可以参考这篇文章。代码入下：