问题描述
输入:一个文本串S,和一个模式串P
输出:若干行,每行包含一个整数,表示s2在s1中出现的位置
在一个母字符串S(文本串)中查找一个子字符串P(模式串)有很多方法。Knuth-Morris-Pratt 字符串查找算法(简称“KMP”)是一种最常见的改进算法,由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。
这个算法针对的是子串有对称属性,如果有对称属性,那么就需要向前查找是否有可以再次匹配的内容。
注意:这里的对称性,不是中心对称,而是中心字符块对称,比如不是abccba,而是abcabc这种对称。
KMP
一般最粗暴的方法,就是匹配失败后,一个字符一个字符往后挪来进行比较,比如:
KMP可以在匹配过程中失配的情况下,有效地多往后面跳几个字符,加快匹配速度。
下面先直接给出KMP的算法流程:
假设现在文本串S匹配到i
位置,模式串P匹配到j
位置
- 当前字符匹配成功(即
S[i] == P[j]
,图一),都令k++
,j++
,继续匹配下一个字符; - 当前字符匹配失败(即
S[i] != P[j]
,图二),则令 k不变,j = next[j]
。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j]
位。
换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文详细阐述),即移动的实际位数为:j - next[j]
,且此值≥1。
next数组(前缀数组)
每一个模式串P都有有一个固定的next数组,它记录着字符串匹配过程中失配情况下可以向前多跳几个字符,当然它描述的也是子串的对称程度,程度越高,值越大,当然之前可能出现再匹配的机会就更大。
这个next数组的求法是KMP算法的关键,看到别的地方到处是数学公式推导,我这里用图示的方法方便大家理解。
- 红色:模式串P当前已经匹配好的相同前后缀
- 蓝色:模式串P当前匹配的位置,就是
j
- 橙色:模式串P当前匹配的最长前缀的后一位,即为
k
如果p[j] == p[k]
,则皆大欢喜, next[j] = next[j - 1] + 1
如果p[j] != p[k]
,只能寻找更短的相同前后缀匹配,我们看下图
- 灰色:当前已经匹配好相同前后缀中的最长公共前后缀
- 紫色:当前已经匹配好相同前后缀中的前缀的后一位
因为红色部分是已经匹配好的,所以既然第二个的后面为灰色部分,第一个的前面和后面也为灰色部分,接下来对应的,第二个前面的也为灰色部分。
查阅蓝色
与紫色
是否匹配。
此时,又回到最初的那一步(递归),求解某个位置的next值是一个循环过程,不断检查 上一位的最长前缀的后一位.
如果相等next[j] = next[k] + 1
,否则 k = next[k]
代码
//优化过后的next 数组求法
void GetNextval(char* p, int next[]) {
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1){
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k]){
++j;
++k;
//较之前next数组求法,改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
next[j] = next[k];
}
else{
k = next[k];
}
}
}