关键点前缀表的aa最长前缀匹配(就这一点我理解了半天!!)----后面我会说明

如果采用暴力解法:当主串的第六个字符b和模式串的第六个字符f不匹配时,就要重头来了

但是:

采用前缀表:

? 1.这玩意儿就不会重头开始,

? 2.而是从上次已经匹配的内容开始匹配,

? 3.找到模式串中的中第三个字符b继续开始匹配(是不是懵逼了!!哈哈哈!!硬着头皮往后看)

> [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tyqKlMue-1654617955804)(Untitled.assets/297CB85B.png)]

**心中的疑问?**凭啥在模式串的第三个字符开始匹配

这就是我们所说的前缀表是如何记录的呢?

前缀表的任务:

当前的位置匹配失败,

找到之前已经匹配上的位置

在重新匹配,

就是某个字符失配时,前缀表会告诉你下一步匹配中,模式串应该跳到哪个位置(怎么跳,再往下读)

我们说了:

再刚刚的匹配的过程,在下标5 的大方遇到不匹配,模式串指向f:如下图所示

然后就莫名其妙的指向了下标2(第三字符)

解释:划重点了哈!!

注意!(先看下)

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

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-50Qzt6BB-1654617955804)(Untitled.assets/29950F6F.gif)]

下标5之前的这部分的字符串(就是aabaa)的最长相等的前缀和后缀字符串是子字符串aa

因为:找到了最长相等的前缀和后缀,匹配失败的位置是后缀子串的后面,

所以:我们找到与其相同的前缀的后面重新开始新匹配就可以了.(这句话好好咀嚼!!!精华)

还是懵逼??哈哈~

你仔细向下模式串的前五个aabbaa与主串中前五个aabaa是一样的对吧?
这是我在模式串找最长前缀与后缀相等的数,是不是就是变相的在主串的子串aabaa中找?(目的找到首次尾部能和头部相同的位置)
这时aa在主串中位置是不是就可确定了???

注意!(再瞅瞅!!)

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

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

四、前缀表的计算

如图:

长度为1的子字符串a,最长相同前后缀的长度为0

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R9wHcA8O-1654617955805)(Untitled.assets/KMP%E7%B2%BE%E8%AE%B25.png)]

按照上面的方法寻找:(子字符串)

aa:最长相同的前后缀的长度为1----------------------------------长度为2
aab:最长相同的前后缀的长度为0---------------------------------长度为3
aaba:最长相同的前后缀的长度为1--------------------------------长度为4
aabaa:最长相同的前后缀的长度为2------------------------------长度为5
aabaaf:最长相同的前后缀的长度为0----------------------------长度为6

对应的最长相同前后缀长度对应的前缀表的元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5rHxPr8f-1654617955805)(Untitled.assets/KMP%E7%B2%BE%E8%AE%B28.png)]

下图利用前缀表找到当字符不匹配时应该指针移动到什么位置:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-M9bBVbvQ-1654617955806)(Untitled.assets/KMP%E7%B2%BE%E8%AE%B22.gif)]

过程分析:

找到不匹配位置,我们要看他的前一个字符的前缀表数值是多少(这里是2)
找前缀表的前一个字符的原因:找到要找前面字符串的最长相同的前缀和后缀

五、前缀表与`next`数组

其实就是一样的,只是具体的实现方式不一样罢了

next数组:就是前缀表,只是很多实现将前缀表进行统一的**减一(右移一位操作)**作为后面的next数组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6H88xp9F-1654617955807)(Untitled.assets/KMP%E7%B2%BE%E8%AE%B24.gif)]

六、时间复杂度----O(n+m)

O(n+m)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8z5NnoQ1-1654617955807)(Untitled.assets/29C539D2.png)]

七、构造`next`数组

定义函数:getNext()

函数参数为指向next的数组的指针和一个字符串

void getNext(int* next,const string& s)

构造``next数组就是计算模式串`,过程步骤分析

1.初始化

//定义两个指针
//j指向前缀末尾位置,i指向后缀末尾位置,并对next数组初始化赋值
int j=-1;
next[0]=j;

说明:

? j初始化-1的原因–前缀表的统一减一操作,

? next[i]表示i(包括i)之前的最长相等的前后缀长度

2.处理前后缀不相同的情况

//因为i=-1,右移一位操作,所以i从1开始

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

如果s[i]与s[j]不相同,进行回退操作

next[j]就是记录这``j`之间的子串相同前后缀的长度

若s[i]与s[j+1]不相同,找j+1前一个元素在next数组里的值(其实就是next[j])

//前后缀不相同
while(j>=0&&s[i]!=s[j+1])
{
    //向前回退
    j=next[j];
}

3.处理前后缀相同的情况

若s[i]yus[j+1]相同,那马旧同事向后移动i和j说明找相同的前后缀,

将``j`(前缀的长度)赋给next[i],记录相同的前后缀长度

//找到相同的前后缀
if(s[i]==s[j+1])
{
    j++;
}
next[i]=j;

整合代码,万朝归元

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