字符串

1、字符串存储

2、字符串的模式匹配

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

• 简单模式匹配

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

• KMP模式匹配

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

3、KMP算法

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

基本概念

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

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_1...P_{next[j]-1}$与$P_{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] = 0。next数组只与模式串有关系，与主串无关。

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

$$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数组应该是什么样的？