字符串

1、字符串存储

2、字符串的模式匹配

 模式匹配是指,在主串中寻找模式串的位置。

  • 简单模式匹配

    依次匹配,如果失配,就后移一位

  • KMP模式匹配

    依次匹配,如果失配,根据next数组后移

3、KMP算法

假设所有下标都是从1开始

基本概念

  • 前缀集合:假设字符串为p{p0,p0p1,...,p0p1...pn1}\{ p_0,\quad p_0p_1, \quad... \quad,\quad p_0p_1...p_{n-1} \}
  • 后缀集合:假设字符串为p{p1,p1p2,...,p1p2...pn}\{ p_1,\quad p_1p_2, \quad... \quad,\quad p_1p_2...p_{n} \}
  • 最长匹配长度:前缀集合与后缀结合中,最长相等元素的长度。
  • 注意:缀集合不包含pnp_n缀集合中不包含p0p_0,如果字串只有一个字符,那么前缀集合和后缀集合都为

KMP算法基本

 假设我们已经有了next数组(下面会介绍next数组求解),假如在主串(S)下标为i,模式串(P)下标为j的位置失配了。

 暴力算法中,我们将会把ij都回溯了,i回溯j个,j回溯到1。KMP算法中,我们让i不进行回溯,仅仅只回溯j。那么,j应该如何回溯呢?

 首先,这里只需要考虑模式串,next数组含义就是,在位置j前面有next[j]-1个字符组成的字符串与从位置1开始往后的next[j]-1个字符组成的字符串是相等的。

 然后,因为主串与模式串在位置j前面的字符串完全相等。我们就只需要把模式串回溯到不相等的位置,最开始不相等的位置,应该是第next[j]个位置。

 解释,因为我们知道P1...Pnext[j]1P_1...P_{next[j]-1}Pjnext[j]...Pj1P_{j-next[j]}...P_{j-1}是相等的,所以只需要从主串当前位置与模式串P[next[j]]开始继续比较即可。也就是,i不变,j = next[j]

Next数组求解

 定义:模式串为p(下标从1开始),next[i]p[1]~p[i-1]组成的子串的最长匹配长度1。

 特殊地,next[1] = 0next数组只与模式串有关系,与主串无关。

next[i]的值与p[i]无关,只与p[i]前面的值有关。

next[j]={0j=1max{k1<k<jp1...pk1=pjk+1...pj1}当此结合不为空时1其他情况next[j] = \begin{cases} 0 & j=1\\ max \{ k \quad|\quad 1<k<j 且 'p_1...p_{k-1}'='p_{j-k+1}...p_{j-1}' \} & 当此结合不为空时\\ 1 & 其他情况 \end{cases}

 上述公式看不懂,问题不大,我也没看懂。

  • 人为求解

    人为求解的话,根据定义来即可,一步一步算

  • 代码求解

    比较复杂

附上代码

// 模式串为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