摘要：第二个是，因为在第个位置，可以有最长为的相同前后缀，依次类推。匹配时分为几种情况字母相同，则和都加，且，因为后缀匹配的长度是前缀的长度加。注意为了方便处理空字符串，我们在反转拼接的时候中间加了，这个字符要保证不会出现在字符串中。
Shortest Palindrome
KMP算法 复杂度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".
时间 O(logN) 空间 O(H)
思路这题要用到部分KMP算法的知识，可以先参考实现StrStr这篇文章。
这题的技巧性非常强，我们观察一下abb这个字符串，将其反转后得到bba，如果只是想得到回文串，那把这个反转的字符串放在前面得到bbaabb就肯定是了。但这明显不是最长的，我们再展示一个技巧，将该反转字符串放在后面再观察一下abbbba，它的前缀和后缀的情况有这些：
a a ab ba abb bba abbb bbba ... ...
显然，这个合并的字符串长度最长的相同前后缀是a，这时候我们把反转后的字符串bba中最后那个a去掉，得到bb，这时候再把bb接到原字符串前面，得到bbabb，这就是最短的回文拼接方法了！
再用一个例子，比如aaba，翻转后得到abaa，然后拼接起来得到aabaabaa，其最长公共前后缀是aa，去掉这个后缀的反转字符串是ab，再接到原字符串上就是abaaba，即最短的回文拼接。
那如何求这个最长公共前后缀有多长呢？这里就要借用KMP算法中的partial match table了，对于刚才的aaba，其连接后为aabaabaa，它的表是：
a a b a a b a a 0 1 0 1 2 3 1 2
第一个a是0，因为没有区分前后缀。第二个a是1，因为在第2个位置，可以有最长为1的相同前后缀(a)，依次类推。这样我们只要知道最后一个字母对应的数，就是这个字符串的最长公共前后缀长度了。那如何求这个表lps[]呢？我们用i表示其前缀的匹配位置，用j表示后缀的匹配位置。然后我们从i=1，j=0，i表示后缀匹配到的位置，j表示前缀匹配到得位置，开始依次向后寻找前缀和后缀的匹配情况。匹配时分为几种情况：
字母相同，则i和j都加1，且lps[i] = j + 1，因为后缀匹配的长度是前缀的长度加1。前缀为j的已经匹配了，现在多一个不就是再加1吗。
字母不相同，且j还不是0时，可以将j回退至lps[j-1]，看看上一个子前缀到哪里结束的，从那里重新匹配。
如果字母不相同，且j是0，已经无法回退，则说明lps[i]也是0了，根本无法匹配的意思，同时i也要加1，开始看下一个字母了。
这里情况2可能多次重复，直到进入了情况3。还不懂的可以看这个文章。
得到这个表后，我们把反转字符串除去相应的后缀，然后加到前面就行了。
注意为了方便处理空字符串，我们在反转拼接的时候中间加了#，这个字符要保证不会出现在字符串中。
在计算表时，当前后缀指针指向字符相同时，lps[i] = j + 1而不是lps[i] = lps[i - 1] + 1; 当j退回0时，lps[i] = 0;
代码public class Solution {
public String shortestPalindrome(String s) {
// 将字符串反转后拼接到后面
String rev = (new StringBuilder(s)).reverse().toString();
String combine = s + "#" + rev;
// 计算LPS表值
int[] lps = new int[combine.length()];
getLPS(combine, lps);
int remove = lps[lps.length-1];
// 去掉后缀后，将反转字符串拼回前面
String prepend = rev.substring(0, rev.length() - remove);
return prepend + s;
}
private void getLPS(String s, int[] lps){
// i是后缀末尾的指针，j是前缀末尾的指针
int j = 0, i = 1;
lps[0] = 0;
// 从j=0，i=1开始找，错开了一位
while(i < s.length()){
// 如果字母相等，则继续匹配，最长相同前后缀的长度也加1
if(s.charAt(i) == s.charAt(j)){
lps[i] = j + 1;
i++;
j++;
// 如果不同
} else {
// 如果前缀末尾指针还没退回0点，则找上一个子前缀的末尾位置
if(j != 0){
j = lps[j - 1];
// 如果退回0点，则最长相同前后缀的长度就是0了
} else {
lps[i] = 0;
i++;
}
}
}
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64599.html
摘要：部分是回文的，在里面找是否有的。这里的范围是，最小是，因为要保证是两个单词，最大是，这时候要找出另一个和他相反的串。判断为回文，可以直接暴力，每个都判断一次。两个方向都找一遍就可能出现重复的情况，注意避免重复。例如，结果应该是。 Palindrome Pairs 链接：https://leetcode.com/problems... 这道题没想出来思路，参考了这个博客的内容：http:...
摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...
摘要：描述给定一组唯一的单词，找出所有不同的索引对，使得列表中的两个单词，，可拼接成回文串。遍历每一个单词，对每一个单词进行切片，组成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...
摘要：题目分析这是上的第题，难度为，判断整型数字是否为回文串，需要注意两点负数都不是回文小于的非负整数都是回文这一题与第题类似，也可以有两种思路数组法和模十法。所以代码可以如下改进能被整除的非整数和负数，返回 题目 Determine whether an integer is a palindrome. Do this without extra space. 分析 这是leetcode上...
Problem 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. Exa...
阅读 2942·2023-04-26 01:32
阅读 1540·2021-09-13 10:37
阅读 2277·2019-08-30 15:56
阅读 1669·2019-08-30 14:00
阅读 3042·2019-08-30 12:44
阅读 1961·2019-08-26 12:20
阅读 1056·2019-08-23 16:29
阅读 3227·2019-08-23 14:44
