KMP用于优化字符串匹配,通过先对模式串操作,然后在模式串和主串比较的时候就会减少那些不必要的比较
操作就是计算模式串的subnext[]数组,subnext[j] 表示的是前 j-1 位这个子串里面, 前k个字符和后k个字符相等,subnext[j] 保存的就是这个k的最大值
KMP未优化版
原理
subnext[]创建
整体思路是借助j-1前面的值来计算第j位的subnext值
初始设置第0位的subnext值是-1,进入循环,使subnext[1]=0(第一位之前只有一位字符,首尾重复相同子串长度为0)
然后进入当j是普通的数的循环,如果第j位和第k位相同,说明在第j+1位的时候,前j位的k值为前j-1位的k减去1,如果sun[j]!=sun[k],此时需要回溯第k位的那个subnext值,让sub[j]和sub[subnext[k]]比较,如果相等就让subnext[j+1]的值是subnext[k]+1
因为此时在比较第j位和第subnext[k]位的时候,也满足字符串前subnext[k]位和后subnext[k]位是重复的,如果还是不相等就继续回溯,直到无法回溯为止(k==-1)
主串和模式串的比较
利用上个函数我们设计的subnext数组,就能减少比较的次数,假设主串检索到第i位,模式串检索到第j位,如果这时候它俩不一样,就从j跳转到subnext[j],因为这时候模式串的前subnext[j]位和后subnext[j]位字符是一样的,所以和主串的i-subnext[j]位字符也是一样的,就不用再比较了。如果pm或者ps有一个到头了,就停止比较
代码
#include<iostream>
#include<string>
using namespace std;
string m, sub;
int subnext[10000];
void creatnext()
{int j = 0; int k = -1; //k表示在前j-1个字符里前后缀相等的字符有k个subnext[0] = -1;while (j < sub.length()-1) //j表示在模式串遍历到的要求的那个next索引 由于最后一个字符与{if (k == -1 || sub[j] == sub[k]) //如果此时的k为负数要停止 避免越界访问//如果此时第j位等于第k位,说明继承k长度的首尾相同字符串成功{ j++; //此时可以算出来下一位也就是subnext[j+1]的值为k+1 (因为sub[j] == sub[k]多了一位)k++;subnext[j] = k;}else k = subnext[k]; //不然就继续回溯}
}
int main()
{getline(cin, m);getline(cin, sub);int pm = 0, ps = 0;int lm = m.length();int ls = sub.length();creatnext();while (pm < lm && ps < ls) {if (ps==-1 ||m[pm] == sub[ps]){pm++;ps++;}else ps = subnext[ps];}for (int i = 0; i < ls; i++)cout << subnext[i] << " ";cout << endl;if (ps == ls) cout << pm - ls;return 0;
}
KMP优化版
原理
大体原理和之前那个一样,优化的就是判断 sub[k] 和 sub[subnext[k]]
假设子串 sub
为 "ABAB"
,传统next数组的构建过程如下:
索引 | 0 | 1 | 2 | 3 |
---|---|---|---|---|
字符 | A | B | A | B |
next | -1 | 0 | 0 | 1 |
当 sub[3]
(字符 B
)匹配失败时,根据 next[3] = 1
,会回溯到 sub[1]
(字符 B
)继续匹配。
但此时 sub[3] = B
和 sub[1] = B
字符相同,意味着即使回溯到 sub[1]
,下一步仍然会匹配失败(因为 sub[1]
与原位置字符相同)。
举个例子
匹配到主串的a和模式串的c不符合,然后模式串就跳到第二位的c了,但是这个c和之前的c是一样的,还是不匹配,所以就重复比较了
这个时候就加入了那个优化, 比较当前这个字符和要跳回去的那个字符是不是相等的,如果相等那就回溯到上上个字符
if (sub[j] != sub[k]) {subnext[j] = k; }
else subnext[j] = subnext[k];
void creatnext() {int j = 0;int k = -1;subnext[0] = -1;while (j < sub.length() - 1) { // 注意循环到j < len-1if (k == -1 || sub[j] == sub[k]) {j++;k++;// 优化next数组if (sub[j] != sub[k]) {subnext[j] = k; } else subnext[j] = subnext[k]; //直接回溯上上个} else k = subnext[k]; }
}