給定一個字符串?s，你可以通過在字符串前面添加字符將其轉換為回文串。找到并返回可以用這種方式轉換的最短回文串。

示例 1：

輸入：s = "aacecaaa"
輸出："aaacecaaa"

示例 2：

輸入：s = "abcd"
輸出："dcbabcd"

提示：

• 0 <= s.length <= 5 * 104
• s?僅由小寫英文字母組成

解析：

要找最短回文字符串，我們可以想 設 s1 = abab將其翻轉 變成 s2 = baba,合并字符串是為 s2 + s1;

這時，它并不是最短字符串，s2+s1 = babab，a可以進行合并。

相當于 abab

和? ? ? ?baba? ?進行kmp

在想想字符串前綴 和 后綴的關系，我們可以想到KMP算法，我們盡可能讓前綴和后綴匹配的個數最多，這時前綴個數后面的就是我們應該反轉的。

class Solution {
public:string shortestPalindrome(string s) {int n = s.size();vector<int> fail (n,-1);for(int i = 1;i < n;i++){int j = fail[i-1];while(j != -1&&s[j+1] != s[i]){j = fail[j];}if(s[j + 1] == s[i]){fail[i] = j+1;}else fail[i] =  j;}int best = -1;for(int i = n - 1;i >= 0;i--){while(best != -1 && s[best+1] != s[i]){best = fail[best];}if(s[best + 1] == s[i]){++best;}}string add = (best == n-1 ? "": s.substr(best+1,n));reverse(add.begin(),add.end());return add+s;}
};

時間復雜度為O（n）;

這里還有一道題就是求給定一個長度為n的字符串，問最短循環節問題。

用kmp做法

分析：1.當字符串是由k個S1拼成的時候,next[n] = k-1個s1長度，所以最小循環節長度為n - next[n]

2. 當字符串為k個完整的s1和一個不完整的s1拼接的時候，設s1長度為L，不完整的為 Z， next[n] = (k-1)L+Z, n - Next[n] = kL + Z - (k -1)L -Z = L

綜上所述：最短長度為n - Next[n]；

字符串哈希：

ａｂａｂ　可以用一個ｆｏｒ循環　

class Solution {
public:string shortestPalindrome(string s) {int n = s.size();int base = 131, mod = 1000000007;int left = 0, right = 0, mul = 1;int best = -1;for (int i = 0; i < n; ++i) {left = ((long long)left * base + s[i]) % mod;right = (right + (long long)mul * s[i]) % mod;if (left == right) {best = i;}mul = (long long)mul * base % mod;}string add = (best == n - 1 ? "" : s.substr(best + 1, n));reverse(add.begin(), add.end());return add + s;}
};

O（ｎ）