#55
KMP
0 次阅读
KMP算法匹配字符串
传统朴素匹配
暴力循环遍历，如果匹配到不一样的字母，文本串指针回到匹配开始位置的下一个位置，模式串指针回到0。很低效很慢。
代码
class Solution {
public:
int strStr(string haystack, string needle) {
int i=0,j=0;
int m=haystack.size();
int n=needle.size();
while(i<m&&j<n)
{
while(i<m&&j<n&&haystack[i]==needle[j])
{
i++;
j++;
}
if(j==n) return i-n;//匹配成功
else {
i-=j;//匹配失败
j=0;
}
i++;//避免死循环
}
return -1;
}
};
KMP算法
先记录相同前后缀（额外建一个next数组记录相同前后缀的长度），匹配失败的时刻，前面都是成功的，当前字母不同而已，在朴素算法中，模式串指针本应��回到0，但是，由于我们记录了相同的前后缀，也就是说，匹配失败时，往前找已经匹配成功的后缀，将相同的前缀与后缀对齐，再从匹配成功的后面开始匹配，目标字符串的指针都不是必须从头开始，优化了速度。下面是例子：
参考上图，我们匹配到后缀ab后，遇到不同的字母f，这时候我们匹配串的指针要从0开始吗？不用啊，匹配了后缀ab，由于我们在前面也有相同的ab（相同前缀），意味着我们可以直接将前缀ab与这后面的ab对齐就行了，此时默认ab已经匹配好，直接从ab后面开始就好了。这个图不是很好，需要点功夫理解。
那么要怎么记录相同前后缀呢？（好问题）
kmp算法的核心在于next数组，next数组是一个用来记录模式串中相同前后缀的长度的数组，不一定要叫next，它就是一个普通的数组。但是，这个数组也不是那么容易理解的，网上的代码都是优化版的，直接看有点难理解。这里是我写的，我觉得比较容易理解。
对了，先看图，黑色为l，红色为r ⬇️
首先next[0]肯定是0了,l=0,r=1
然后如果pattern[l]==pattern[r],那么next[r]=l+1=1
再递增l++,r++ ⬇️
接着就是循环执行了，一直往右走直到————pattern[l]!=pattern[r]
此时l=next[l-1]=1，往前找（循环执行），还是不对，再l=next[l-1]=0，还是不对 ⬆️
但是此时l=0，不能再往前了，说明没有相同前后缀了，即next[r]=0，⬇️
重复执行以上步骤，直到r==len，next数组全部建好
简陋版next数组代码
class Solution
{
public:
vector<int> &buildNext(string &a)
{
int len = a.length();
vector<int> next(len, 0);
int l = 1, r = 2; //防止next[l-1]不存在下标
if (a[0] == a[l])//next数组前两位的处理
next[1] = 1;
else
next[1] = 0;
while (r < len)
{
while (r < len && a[l] == a[r])//如果相等，则记录相同前后缀长度
{
next[r] = l + 1;
l++;
r++;
}
while (a[l] != a[r])//如果不想等，则往前找
{
l = next[l - 1];
if (l == 0 && a[l] != a[r])//如果找到最前面都找不到，就是没有了
{
next[r] = 0;//以下标为r到字母结尾的相同前后缀长度为0，也就是没有相同前后缀
r++;//r右移，避免死循环
break;
}
}
}
return next;
}
};
优化版next数组代码
for(int i = 2, j = 0; i <= m; i++){
while(j and p[i] != p[j + 1]) j = next[j];
if(p[i] == p[j + 1]) j++;
next[i] = j;
}