字符串
1、字符串存储
2、字符串的模式匹配
模式匹配是指,在主串中寻找模式串的位置。
-
简单模式匹配
依次匹配,如果失配,就后移一位
-
KMP模式匹配
依次匹配,如果失配,根据
next数组
后移
3、KMP算法
假设所有下标都是从1开始
基本概念
- 前缀集合:假设字符串为
p
, - 后缀集合:假设字符串为
p
, - 最长匹配长度:前缀集合与后缀结合中,最长相等元素的长度。
- 注意:前缀集合不包含,后缀集合中不包含,如果字串只有一个字符,那么前缀集合和后缀集合都为空。
KMP算法基本
假设我们已经有了next
数组(下面会介绍next
数组求解),假如在主串(S
)下标为i
,模式串(P
)下标为j
的位置失配了。
暴力算法中,我们将会把i
和j
都回溯了,i
回溯j
个,j
回溯到1。KMP算法中,我们让i
不进行回溯,仅仅只回溯j
。那么,j
应该如何回溯呢?
首先,这里只需要考虑模式串,next数组含义就是,在位置j
前面有next[j]-1
个字符组成的字符串与从位置1开始往后的next[j]-1
个字符组成的字符串是相等的。
然后,因为主串与模式串在位置j前面的字符串完全相等。我们就只需要把模式串回溯到不相等的位置,最开始不相等的位置,应该是第next[j]
个位置。
解释,因为我们知道与是相等的,所以只需要从主串当前位置与模式串P[next[j]]
开始继续比较即可。也就是,i不变,j = next[j]
Next
数组求解
定义:模式串为p
(下标从1开始),next[i]
:p[1]~p[i-1]
组成的子串的最长匹配长度加1。
特殊地,next[1] = 0
。next
数组只与模式串有关系,与主串无关。
next[i]
的值与p[i]
无关,只与p[i]
前面的值有关。
上述公式看不懂,问题不大,我也没看懂。
-
人为求解
人为求解的话,根据定义来即可,一步一步算
-
代码求解
比较复杂
附上代码
// 模式串为p
int next[p.size] = {0};
next[1] = 0;
for(int i = 2 ; i < p.size; i++){
int j = next[i-1];
while(true){
if(j==0 || p[j] == p[i-1]){
next[i] = j;
break;
}else {
j = next[j];
}
}
}
KMP算法优化,NextVal
数组求解
前面提到next[j]
值与p[j]
无关,只与前前面的字符串有关。如果在j
失配,也就是p[j]!=s[i]
的话,那么下一个j
回溯到next[j]
的位置。如果此时p[next[j]]!=s[i]
的话,那么还得继续回溯到p[next[next[j]]]
,不如我们在构建next
数组就把这种情况规避掉。因此,有了下列优化算法。
其他情况与上述next
数组构造一样,不同的是,如果p[j]==p[next[j]]
,就把上面代码改为如下:
...
if(j==0 || p[j] == p[i-1]){
if(p[j] != p[i]) next[i] = j;
else next[i] = next[j];
break;
}else {
j = next[j];
}
...
如何在考试中人为求解呢?
答:我的建议是,先求出next
数组,然后在next
数组的基础上,再看。如果p[j]==p[next[j]]
,就修正nextval[j]=nextval[next[j]]
。否则不变。因为是从前往后的,所以我们在next
和已修正nextval
的基础上,构造出nextval[j]
。
如题所示,"ababaaababaa"
的nextval
数组应该是什么样的?
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 | a | b | a | b | a | a | a | b | a | b | a | a |
next |
0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 4 |
nextval |
0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 | 4 |