[Leetcode][第214题][JAVA][最短回文串][KMP][RK]

待我称王封你为后i 2022-12-02 04:09 169阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

###### 1. 字符串哈希 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

**复杂度**  
![在这里插入图片描述][20200829162249256.png_pic_center]

class Solution { 
        public String shortestPalindrome(String s) { 
            int n = s.length();
            int base = 131, mod = 1000000007;
            int left = 0, right = 0, mul = 1;
            int best = -1;
            for (int i = 0; i < n; ++i) { 
                left = (int) (((long) left * base + s.charAt(i)) % mod);
                right = (int) ((right + (long) mul * s.charAt(i)) % mod);
                if (left == right) { 
                    best = i;
                }
                //倒叙进制
                mul = (int) ((long) mul * base % mod);
            }
            String add = (best == n - 1 ? "" : s.substring(best + 1));
            StringBuffer ans = new StringBuffer(add).reverse();
            ans.append(s);
            return ans.toString();
        }
    }

###### 2. KMP ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

**复杂度**  
![在这里插入图片描述][20200829162324828.png_pic_center]

class Solution { 
        public String shortestPalindrome(String s) { 
            int n = s.length();
            int[] fail = new int[n];
            Arrays.fill(fail, -1);
            //next数组
            for (int i = 1; i < n; ++i) { 
                int j = fail[i - 1];
                while (j != -1 && s.charAt(j + 1) != s.charAt(i)) { 
                    j = fail[j];
                }
                if (s.charAt(j + 1) == s.charAt(i)) { 
                    fail[i] = j + 1;
                }
            }
            int best = -1;
            for (int i = n - 1; i >= 0; --i) { 
                while (best != -1 && s.charAt(best + 1) != s.charAt(i)) { 
                    best = fail[best];
                }
                if (s.charAt(best + 1) == s.charAt(i)) { 
                    ++best;
                }
            }
            String add = (best == n - 1 ? "" : s.substring(best + 1));
            StringBuffer ans = new StringBuffer(add).reverse();
            ans.append(s);
            return ans.toString();
        }
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#### 【总结】 ####

###### 1. [【数据结构与算法】字符串匹配 BF算法 RK算法][BF_ RK] ######

###### 2.[【数据结构与算法】字符串匹配 KMP 算法][KMP] ######

###### 3.RK算法 本质是hash KMP算法关键求next数组 ######

转载链接：https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d13c3c68fcd146f799f4d43722c86fbf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/fa35e4af5c714b3886db3c317fdd83f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/d0571dd6970d41e39622d81ad37c705d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/04eafd45812441ee92c066e40677e0dd.png
[20200829162249256.png_pic_center]: /images/20221123/6e9e44ae966d435caa0170653e7c336f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/ae025524e7df4832b835d79526fdabcb.png
[20200829162324828.png_pic_center]: /images/20221123/f3ac2c76beba4cbaafa05853b11cdec1.png
[BF_ RK]: https://blog.csdn.net/dadongwudi/article/details/108206019
[KMP]: https://blog.csdn.net/dadongwudi/article/details/108222575