[LeetCode]Shortest Palindrome

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

	class Solution {
	public:
	string shortestPalindrome(string s) {
	if(!s.size())return "";
	string rev = s, sCopy = s;
	reverse(rev.begin(), rev.end());
	s = s + "#" + rev;
	int len = s.size();
	vector<int> next(len + 1, -1);
	int i = 0, k = -1;
	while(i < len)
	{
	if(k == -1 || s[i] == s[k])
	next[++i] = ++k;
	else
	k = next[k];
	}
	int palinLen = next[len];
	string mirror = sCopy.substr(palinLen);
	reverse(mirror.begin(), mirror.end());
	return mirror + sCopy;
	}
	};

view raw Shortest Palindrome.cpp hosted with ❤ by GitHub