题目

题目来源：力扣（LeetCode）

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

输入：s = “aacecaaa”
输出：”aaacecaaa”
示例 2：

输入：s = “abcd”
输出：”dcbabcd”

思路分析

我们可以把题目给定的字符串 s 反转过来，得到 reverse 字符串，然后在 s 和reverse之间加上一个 # 字符作为分割，拼成一个新的pattern字符串，然后用KMP中计算pattern最长前后缀的方法，得到pattern的最长公共前后缀ABA，然后把reverse放在前面，s放在后面，删掉中间重复的一组ABA，就得到结果了。

image.png
因为我们需要得到的只是pattern的next数组中的最后一个值，所以commpute_next只需要返回最后一个值就可以了。

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  6.  const shortestPalindrome = (s) => {
  7.   //  将给定的字符串 s 反转过来，得到 reverse 字符串
  8.   const reverse_s = s.split('').reverse().join('');
  9.   // 在 s 和 reverse 之间加上一个 # 字符作为分割，拼成一个新的pattern字符串
  10.   const pattern_str = s + "#" + reverse_s;
  11.   // 计算pattern最长前后缀，得到pattern的最长公共前后缀
  12.   const next = new Array(pattern_str.length).fill(0);
  13.   getNext(next, pattern_str)
  15.   const maxLen = next[pattern_str.length - 1]; // 最长回文前缀的长度
  16.   // const add = s.substring(maxLen).split('').reverse().join('');
  17.   // 把reverse放在前面，s放在后面
  18.   const add = reverse_s.substr(0, reverse_s.length - maxLen);
  19.   return add + s;
  20. };
  22. // 计算next数组(next数组不减一的实现)
  23. function getNext(next, s) {
  24.   next[0] = 0;
  25.   let j = 0;
  26.   for (let i = 1; i < s.length; i++) { // 注意i从1开始
  27.     while (j > 0 && s[i] != s[j]) { // 前后缀不相同了
  28.       j = next[j - 1]; // 向前回溯
  29.     }
  30.     if (s[i] == s[j]) { // 找到相同的前后缀
  31.       j++;
  32.     }
  33.     next[i] = j; // 将j（前缀的长度）赋给next[i]
  34.   }
  35. }

参考阅读：
https://leetcode-cn.com/problems/implement-strstr/solution/dai-ma-sui-xiang-lu-kmpsuan-fa-xiang-jie-mfbs/ https://leetcode-cn.com/problems/shortest-palindrome/solution/tu-jie-kmpsuan-fa-by-yangbingjie/