字符串：前缀表不右移，难道就写不出KMP了？

代码随想录

修改于 2020-10-09 20:30:05

6030

本文：https://github.com/youngyangyang04/leetcode-master已经收录，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库，有空看一看一定会有所收获，如果对你有帮助也给一个star支持一下吧！

其实前缀表到底要不要减一（右移），主要看代码如何实现。

昨天一位读者做了实验并且和我深入讨论了这个问题，感觉这位小伙说的非常有道理！我也亲自写了一下代码，并且在leetcode上通过了，所以要和大家分享一下。

我在文中字符串：听说你对KMP有这些疑问？在前缀表不减一的情况下，依然使用j=next[j]来进行回退，确实会出现死循环。

但完全可以换一种回退方式，应该找j=next[j-1] 来进行回退。

主要就是j=next[x]这一步最为关键！

我给出的getNext的实现为：（前缀表统一减一）

void getNext(int* next, const string& s) {
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回溯
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

此时如果输入的s为aabaaf，对应的next为-1 0 -1 0 1 -1。

这里j和next[0]初始化为-1，整个next数组是以前缀表减一之后的效果来构建的。

那么前缀表不减一来构建next数组，代码如下：

    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下表的操作
                j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

此时如果输入的s为aabaaf，对应的next为 0 1 0 1 2 0，（其实这就是前缀表的数值了）。

那么用这样的next数组也可以用来做匹配，代码要有所改动。

28. 实现 strStr() C++代码

前缀表统一减一的版本：28. 实现 strStr()

直接使用前缀表（不减一）版本实现如下：

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下表的操作
                j = next[j - 1]; // 从j-1对应的回退值开始回退
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1]; // 这里要找j前一位的对应的回退位置了
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

459.重复的子字符串 C++代码

前缀表统一减一的版本：459.重复的子字符串

直接使用前缀表（不减一）版本实现如下：

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下表的操作
                j = next[j - 1]; // 从j-1对应的回退值开始回退
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) { 
            return true;
        }
        return false;
    }
};

如有疑问欢迎来找我讨论哈，我也在讨论中学习了很多！

在留言区留下你的思路吧！

-------end-------

我是程序员Carl，哈工大师兄，先后在腾讯和百度从事技术研发多年，利用工作之余重刷leetcode。
我的B站（里面有我讲解的算法视频以及编程相关知识）：https://space.bilibili.com/525438321
我的github：https://github.com/youngyangyang04
更多精彩算法文章尽在：代码随想录，关注后，回复「Java」「C++」「python」「简历模板」等等，有我整理多年的学习资料，可以加我微信，备注「个人简介」+「组队刷题」，拉你进入刷题群（无任何广告，纯个人分享），每天一道经典题目分析，我选的每一道题目都不是孤立的，而是由浅入深一脉相承的，如果跟住节奏每篇连续着看，定会融会贯通。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-09，如有侵权请联系 cloudcommunity@tencent.com 删除

c++