AlgoPressAppearance
0214-最短回文串
https://leetcode.cn/problems/shortest-palindrome
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa"
输出："aaacecaaa"
示例 2：
输入：s = "abcd"
输出："dcbabcd"
提示：
0 <= s.length <= 5 * 104
s 仅由小写英文字母组成
思路1 【官方 KMP】
首先我们可以肯定，对字符串 s 去掉第一个字符，将后面的 s[1..n] 反序添加到前面，就可以得到回文串 而题目要找的数字串长度肯定小于等于这个长度，即 s'.Length <= s.Length -1 那么具体可以小多少呢，我们如果从 s[0] 开始找出s[0]开始的最大的回文串，那么剩下的部分，反序之后，就是要添加的字符串。 详情：参考题解 https://leetcode.cn/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/
比较字符串的算法可以使用KMP算法：
将源字符串添加 # 和 反序 s', 计算最后的公共前后缀即为最大回文的长度 如 aacecaaa#aaacecaa 最大的公共前后缀就是 aa 为2 那么添加的数就是 s[2-1,length] 反序
添加 # 的原因是, 如果重复的字符串如 aaa 直接添加 aaa后 aaaaaa 计算的结果是 6 但是实际需要的是 3 ，所以 aaa#aaa 得出的是正确的结果。
参考代码
csharp
public class Solution {
public string ShortestPalindrome(string s) {
string str = s+"#";
for(int i=s.Length-1;i>=0;i--){
str+=s[i];
}
//计算 kmp next 数组
int prefixIndex = 0;
int[] next = new int[str.Length];
next[0] = 0;
for(int nextIndex = 1; nextIndex < str.Length; nextIndex++){
while(prefixIndex > 0 && str[prefixIndex] != str[nextIndex] ){
prefixIndex = next[prefixIndex-1];
}
if(str[prefixIndex] == str[nextIndex]){
prefixIndex++;
next[nextIndex] = prefixIndex;
}
}
int index = next[str.Length-1];
//打印 next 数组
// Console.WriteLine(str);
// for(int i=0; i<next.Length; i++){
// Console.Write("{0}",next[i]);
// }
string result = "";
for(int i=s.Length-1; i>=index; i--){
result+=s[i];
}
result += s;
return result;
}
}
思路：复习20220520
输入：s = "aacecaaa"
输出："aaacecaaa"
题目要求在最前面增加字符串变成回文串。
- 首先考虑最大解，我们将数字反序追加到前面，这样肯定是回文串，比如 ananab 变成
banana+ananab，增加一个加号为了便于说明 - 然后我们考虑第一个字符肯定是回文的，所以不需要转换第一个字符 则变成
banan+a+nanab - 但实际上中间有 anana 就是回文的，所以实际上我们只要复制一个b
b+anana+b - 现在问题就是如何找到 anana 这个最小的回文串
- 我们可以通过在原来字符后面增加一个 # 号，然后将字符串反转追加，有 ananab#banana ，因为是回文的，所以他翻转的也是一样的字符，所以问题变成找到公共前后缀的方式
- 我们可以使用 KMP 算法中求解 next 数组的方式来求取公共前后缀
csharp
public class Solution {
public string ShortestPalindrome(string s) {
string str = s+"#";
for(int i = s.Length-1;i>=0;i--){
str+=s[i];
}
//求取next数组 ananabanana , aabaabaaf
int j = 0;
int[] next = new int[str.Length];
for(int k = 1; k<str.Length; k++){
//不匹配
while(str[k] != str[j] && j != 0){
j = next[j-1];
}
//匹配
if(str[k] == str[j]){
j++;
next[k] = j;
}
}
int index = next[str.Length-1]; //最后的公共前后缀长度
//Console.WriteLine("index={0}",index);
string result = "";
for(int k=s.Length-1;k>=index; k--){
result+=s[k];
}
result+=s;
return result;
}
}
复习：20220705
差不多是抄出来的，kmp还需加强
csharp
public class Solution {
public string ShortestPalindrome(string s) {
//第1步：拼接字符串为 abcde#ebcda的格式
string str = s + "#";
for(int i=s.Length-1; i>=0; i--){
str+=s[i];
}
//第2步：求公共前后缀的数组长度 KMP next 数组
int[] next = new int[str.Length];
//从第1个开始求
int j=0;
for(int i=1; i<str.Length; i++){
while(j != 0 && str[i] != str[j]){
j = next[j-1];
}
if(str[i] == str[j]){
j++;
next[i] = j;
}
}
//找出 index，即为公共前后缀，把剩余部分反向加入进去
int index = next[str.Length-1];
string result = "";
for(int i=s.Length-1; i>=index;i--){
result += s[i];
}
result+=s;
return result;
}
}