乐趣区

关于算法:小白KMP算法-讲清楚next数组生成代码

jiezi

KMP 算法解说的很多，清晰的很少，在此写一个汪汪都能看懂的通俗易懂直观的精讲。文末会给出学习倡议。

KMP 算法的由来和本文术语解释

KMP 算法的中文名称为疾速模式匹配算法，是为了疾速解决在一个字符串中查找另一个字符串的问题。（为了不便形容，要找到的那个字符串叫模式串，要搜寻的那个范畴叫文本串。比方要求在字符串 abbaf 中找到字符串 baf，baf 就是模式串，abbaf 就是文本串）。

针对这种问题，咱们其实很容易想到一种暴力的算法，那就是一个一个比。

不难发现，遇到不匹配的状况时，模式串每次都是傻傻的挪一下，而后再一位一位地去比拟。

暴力太傻了吧，所以就有了 KMP 算法，让模式串迈开腿，可能大步往前走。但大步走也不是瞎走，不然走过了相等的村就没有相等的店了，得有点策略地走，于是有了 next 数组。这个数组的名字起的其实还是有点形象的，代表比到某一位不匹配了下一个比哪一位，像一个领导手册似的。

为什么要有 next 数组以及对他的直观了解

next 数组就是一个模式串的行为领导手册。

当红色的 C 和 A 不匹配时，黄色的 AB 和 AB 曾经比拟过了，而模式串 p 中橙色和黄色局部是相等的，那挺好，黄色 AB 都跟文本串比过了，橙色的 AB 就能够省点事，这样间接比拟绿色箭头处就能够了。

那咱们怎么决定从哪一位开始比拟呢。这里就引入了前后缀的问题。要找到模式串 p 中不匹配地位 A 后面的子串 ”ABCAB” 中雷同的前缀和后缀，这个雷同的局部就是能够偷懒不必比的局部了。那如果雷同的前缀和后缀有很多取哪个呢？那必定取最长的呀，这样就能偷更多懒，下一轮不必比的就更多了。

所以，为了晓得如何偷懒，咱们定义了一个没有名字的表，这个表通知咱们以某个地位的字符结尾的字符串，最长的雷同前后缀的长度是多少。

看下图了解最长雷同前后缀。

那为啥要晓得长度呢？长度其实就是下一次的下标。以下图为例，A 后面以 B 为结尾的字符串 ABCAB 的最长雷同前后缀的长度为 2，那下一轮比拟的就是 2 地位的 C，后面的不必比了。

那么这个时候 next 数组就出场了，他就和这个不出名的表有关系，但又不齐全一样，但实质上 next 都是由这张表变来的。

理论实现时依据须要可能把这个表的所有元素 -1，也可能所有元素右移之类的(右移的话 AC 不匹配时就不必看前一位的 next 了，间接看本人地位的就行，因为他人的右移到本人的地盘了)。我也不晓得为啥就要 - 1 之类的，除了让 KMP 更难了解以外，如同啥用没有。

本文就不进行这些花里胡哨的操作了。

精髓！next 数组的代码实现 图预警

到当初大部分人预计都能手写一个模式串的 next 的数组了，毕竟肉眼看最长的雷同前后缀也还行。然而看到代码实现的时候还是会懵的不行，这是因为真的太奇妙了，其中甚至用到了递归的思路。为了好了解，我就间接将前文图中推导的表作为 next 数组。

递归思路如何画图了解

1. 定义两个指针，cur 是指向以后地位的，代表要求以 cur 地位字符结尾的最长雷同前后缀，recur 有两个含意，可能是上一轮循环之后传过来的（代表以前一个字符结尾的最长雷同前后缀），也可能是递归的时候递归到的，反正也不必管这么多，反正 recur 在赋值给 next 时候就会指向最长雷同前缀的下一位。

2. 画图了解递归的思路

如图显示的是进入某一轮循环，cur=17,recur= 8 时递归代码的执行过程。

next[cur-1]= next[16] = 8 代表红色的两个框雷同（时刻牢记 next 的含意）

  • 如果这个时候 s[cur] == s[recur]阐明 next[cur] = recur+1=9, 示意最长雷同前后缀长度为 9。
  • 如果这个时候 s[cur] != s[recur]阐明 next[cur] <= recur, 这里就要用到递归了。红色框中字符相等，咱们求的最长雷同后缀是以 cur 结尾的那一撮，那就能够转化为求 recur- 1 结尾的最长雷同前后缀, 即 next[recur-1]。依据 next[recur-1]=next[7]的值 3 能够晓得右边两个绿框雷同，所以图中四个绿框就都雷同了。然而咱要的其实还是左右边上的两个绿框相等。
  • 接下来就还是循环第一步，recur 指针移到新的红色地位。如果这时 next[cur] == next[recur]的话，next[cur] = recur+1=4。如果不相等，那 recur 还要递归挪动，直到 recur = 0 时不能再挪动或者遇到相等的状况。
void getNext(int* next,string& s){
        int recur = 0;
        next[0] = recur;
        for(int cur = 1;cur < s.size();cur++){while(recur > 0 && s[cur] != s[recur]){recur = next[recur-1];// 递归局部
            }
            if(s[cur] == s[recur]){//recur= 0 或者相等的时候
                recur++;
            }
            next[cur] = recur;
        }
    }

计算 next 时初始化值如何确定

另外，代码的初始条件也不能看着答案想当然。next[0]= 0 是因为只有 s[0]一个元素时，不存在最长雷同前后缀。j 的初始化有两种方法能够思考，一种是察看 for 循环中的 next[i]=j，所以 next[0]= 0 时 j 就是 0。也能够在计算 next[1]的时候看看，须要 j 是几能力失去正确答案。

计算结果的图形化解释

以字符串 ”ABCABA” 为例运行代码，两头过程如下图。

KMP 算法的代码实现

利用 next 实现 KMP 的要害要点

有了 next 数组之后，如何利用他呢？大体来说是管制模式串指针和文本串指针的挪动，直到达到文本串开端或者模式串开端。其中有以下几个要点：

  1. 遇到某一位不匹配时，要依据 这一位前一位的 next 值 确认接下来要比拟的是模式串中的哪一位(也就是模式串指针指向哪里)。
  2. 1 中扭转了模式串指针之后，文本串指针不能挪动到下一位，而是要放弃不变，持续比拟，否则就会越过一些值。所以 for 外部须要有 while 循环，而不能写 if 让其进入下一轮 for 循环。
    int j = 0;
        for(int i = 0;i < haystack.size();i++){while(j > 0 && needle[j] != haystack[i]){// 对应要点 2 的 while 循环
                cout << "pattern[" << j << "]" << "!=" << "s[" << i << "]" << endl;
                cout << "j 从" << j << "变为" << next[j-1] << endl;
                j = next[j-1];// 对应要点 1 的找前一位
            }
            if(needle[j] == haystack[i]){cout << "pattern[" << j << "]" << "==" << "s[" << i << "]" << endl;
                j++;
            }
            if(j == needle.size()) return i - needle.size()+1;// 完结坐标 - 长度 +1= 起始坐标}

运行后果的图形化解释

退出必要的正文运行，后果如下，与图片齐全对应。

pattern[0]==s[0]
pattern[1]==s[1]
pattern[2]==s[2]
pattern[3]==s[3]
pattern[4]==s[4]
pattern[5]!=s[5]
j 从 5 变为 2
pattern[2]==s[5]
pattern[3]==s[6]
pattern[4]==s[7]
pattern[5]==s[8]

最初的学习倡议

找个很长的字符串，按我的推导把 getNext 函数人工推导一次，这样就拿了解 recur 变动的奇妙之处了。当递归不好了解时，肯定要联合解释递归的那两个红框和绿框去思考。

退出移动版