最短回文串 shuitang

题目

214. Shortest Palindrome

难度困难205

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.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

解法

解法一

又是字符串,又是回文串的问题……关键是这题是怎么思考的?最短的回文串 =》 最长的回文子串 =》如何快速判断一个字符串是不是回文串 =》字符串哈希 =》 字符串哈希可以从上一步O(1) 得到,所以得到了一个 O(n) 的算法。算法如下:

class Solution {
public:
    string shortestPalindrome(string s){
        typedef long long LL;
		int base = 173;
		int mod = 1000000007;

		LL val = 0;
		LL rev_val = 0;
		int res = 0;
		LL power = 1;
		for(int i=0;i<s.length();++i){
			val = (val*base % mod + int(s[i]))%mod;
			rev_val  = (rev_val + (int)(s[i]) * power )%mod;
            power = power * base % mod;
			if(val == rev_val){
				res = i;
			}
		}
		res = s.length() -1 - res;
		string ans;
		for(int i=0;i<res; ++i){
			ans.push_back(s[s.length()-1-i]);
		}
		ans = ans + s;
		return ans;
	}
        
};

解法二

KMP 算法思考此题。如上面分析的那样,要寻找一个最长的回文子串?什么意思呢?等价于寻找 s 的一个逆字符串 s’,并在其中寻找一个最长匹配!!!

这就是 KMP 算法可以直接解决的。