数据结构：KMP算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构：KMP算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.何为KMP算法

KMP算法是由Knuth、Morris和Pratt三位学者发明的，所以取了三位学者名字的首字母，叫作KMP算法。

2.KMP的用处

KMP主要用于字符串匹配的问题，主要思想是当出现字符串不匹配时，我们可以知道一部分之前已经匹配过的的文本内容，利用这些信息从而避免从头再开始匹配。

但是如何才能知道之前已经匹配过的内容呢？这是KMP算法的核心，也是KMP算法里面的next数组的用处。

3.最长相等前后缀

一个字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续字串

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

前缀表也就是next数组要求的是最长相等前后缀的长度，例如a的最长相等前后缀为0，aaa得到最长相等前后缀为2，aaba的最长相等前后缀为1。

4.next数组(前缀表)

KMP的核心就是next数组，当模板串和主串不匹配时，next数组是用来让模板串知道应该从哪里再开始匹配。

next数组记录下标i之前(包括i)的字符串中，有多大长度的相等前后缀。

这里借用了代码随想录的图片

数据结构：KMP算法,数据结构,数据结构

比如我们要在文本串aabaabaafa中寻找模板串aabaaf，在b和f之前发现匹配不了，如果用暴力算法，就要从头开始匹配，文本串和模板串都需要进行回退，时间复杂度是很高的，但如果我们使用KMP算法，next数组记录了f之前有多大长度的相等前后缀，也就是我们知道了之前匹配过的内容，就会从上次已经匹配的内容开始匹配，这里为什么能这样呢？我是这样理解的：

文本串: aabaabaafa 用i遍历

模板串：aabaaf 用j遍历

在b和f时不相同了，这时候我们不想再匹配我们已经匹配过的，也就是说我们不想i回退，而是一直向前走，那我们就要j进行回退，回退到什么位置呢，前面已经匹配到了，说明已经匹配过的文本串aabaa中含有模板串一部分内容，又因为前后缀有相等的部分。所以我们回退到前后缀相等的前缀位置，因为和文本串是相同的，所以aabaa的后缀aa和文本串的aabaa的后缀aa是相等的，又有aabaa的前缀aa和后缀aa是相等前后缀，所以前缀aa和文本串aabaa的后缀aa相等，我们回退到aabaa的b即可避免再次匹配aabaa的前缀aa，这样也可以保证模板串aabaa的前缀aa是已经匹配过的。

f之前这部分的字符串（也就是字符串aabaa）的最长相等前后缀是aa ，因为找到了最长相等的前后缀，匹配失败的位置是后缀的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

5.如何计算next数组

 例如a a b a a f

 下标0 1 2 3 4 5

next 0 1 0 1 2 0

当下标为0时，长度为前1个字符的字串a，最长相等前后缀的长度为0

当下标为1时，长度为前2个字符的字串aa，最长相等前后缀的长度为1

依次类比，可以得到next数组，也就是前缀表

可以看出模板串和next数组对应位置的数字表示的是下标i之前(包括i)的字符串中，有多大长度的最长相等前后缀。

数据结构：KMP算法,数据结构,数据结构

当我们找到不匹配的位置时，就要看它前一个字符的next数组的值是多少，因为我们要找前面字符串的最长相等前后缀，所以要看前一位的next数组的值，前一个字符的next数组值为2，所以我们把下标j移动到2的位置继续匹配，这样就可以匹配到了。

6.next数组实现

主要是处理前后缀相等和不相等的情况，我们首先定义一个getNext函数来构造next数组，参数为指向next数组的指针，和一个字符串

void getNext(int* next,string& s)

接着我们对其进行初始化，定义两个指针i和j，j指向前缀末尾，i指向后缀末尾，对next数组进行初始化赋值

int j=0;
next[0]=j;

next[i]表示i(包括i)之前最长相等的前后缀长度，就是j，所以初始化next[0]=j

6.1前后缀不相同

j=0，所以我们从i=1开始，遍历文本串，就像这样

for(int i=0;i<s.size();i++)

j首先要保证是大于0的，因为下面j要回退，然后就是s[i]和s[j]的比较，如果s[i]和s[j]不相同，j就要找前一位对应的回退位置，因为这里j之前的前缀已经和i的后缀不相等了，所以我们就要j进行回退。

while(j>=0&&s[i]!=s[j])
{
   j=next[j-1];
}

6.2前后缀相同

如果是s[i]和s[j]相同，这时候只要同时移动i和j，这时候找到了相同的前后缀，我们要把j的值赋值给next[i]，因为next[i]记录相同前后缀的长度

if(s[i]==s[j])
{
   j++;
}
next[i]=j;

完整代码如下：

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 = next[j - 1]; 
        }
        if (s[i] == s[j])
        {
            j++;
        }
        next[i] = j;
     }
}

7.例题

  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=next[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];
                    }
                    if(haystack[i]==needle[j]){
                        j++;
                    }
                    if(j==needle.size()){
                        return (i-needle.size()+1) ;
                 }
                }
                return -1;
            }

这道题很明显是字符串匹配的问题，所以我们使用KMP算法，首先是next数组的构建，这是模板，直接写就行，然后就是模板串和文本串的匹配，如果不相同，那j就回退到next[j-1]，如果相同，j就直接向后移动即可，当j和模板串的长度相等时，此时i一定是大于等于模板串的长度的，因为i之前的文本串是包含模板串的，所以我们用i-模板串的长度+1就是第一个匹配项的下标了。文章来源地址https://www.toymoban.com/news/detail-761393.html

到了这里，关于数据结构：KMP算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！