# Ch4

# 模式匹配

i: 主串当前待比较的字符位置
j: 模式串当前待比较的字符位置

字符串模式匹配，在主串中找到与模式串相同的子串

# 暴力算法

遍历主串，从每个和第一个字符相同的位置开始，继续比较后继字符
时间复杂度： $O(mn)$ （主串长度 n，模式串长度 m）

# KMP 算法

https://www.bilibili.com/video/BV1PD4y1o7nd/?spm_id_from=333.1387.homepage.video_card.click&vd_source=1a7d8f596f3dfe40fee34c858ed47e73
这个讲得好

KMP 算法中 i 永远不递减

前缀：除了最后一个字符外所有的头部子串
后缀：除了第一个字符外所有的尾部子串

PM 数组
方法：算出所有前缀的前缀和后缀的最长公共子串的长度，并保存在数组中（PM，部分匹配值）
从头开始，右滑位数 = 已匹配的字符数 - 对应的部分匹配值（最后一个匹配的字符的 PM）
时间复杂度： $O(m+n)$
next 数组
next 数组代表匹配的时候子串中可以跳过匹配的字符个数

$next[j] = PM[j-1] + 1$

将模式串的 PM 表右移一位并整体 + 1，左边空缺用 0 来填充，右边溢出舍去

在上面方法中，串的编号是从 1 开始的

当模式串在位置 j 与主串不匹配时，模式串应该向右滑动的位数 = j - next [j-1]

next 数组的一般公式

第 1 个是 0，第 2 个是 1
当前位置前面的串的相等的最长的前缀和后缀的长度 + 1
前缀后缀都不相等，填 1

直接看代码

KMP

void get_next(SString T, int nexxt[]){
    int i = 1, j = 0;   //i指向当前要计算next[i]的位置，j表示上一个最长前后缀长度
    next[1] = 0;
    while(i < T.length){
        if(j == 0 || T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

next [0] 是不用的

KMP 匹配算法

KMP

int index_KMP(SString S, SString T, int next[]){
    int i = 1, j = 1;
    while(i <= S.length && j <= T.length){
        if(j == 0 || S.ch[i] == T.ch[j]){   //表示模式串已经回退到不能再回退的位置,此时必须让主串指针i前进一步，模式串从第一个字符重新开始匹配
            ++i;
            ++j;
        }else{
            j = next[j];
        }
    }
    if(j > T.length) return i - T.length;
    else return 0;
}

nextval 数组
如果 $p_j$ 和 $p_{next[j]}$ 相等，让 next [j] 的值等于 next [next [j]]，一直递归下去
如果跳转后的位置字符和当前字符相同，那就直接跳到更前面的位置（即 nextval [j]），避免无效比较

nextval

void get_nextval(SString T, int nextval[]){
    int i = 1, j = 0;
    nextval[1] = 0;
    while(i < T.length){
        if(j == 0 || T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            if(T.ch[i] != T.ch[j])
                nextval[i] = j;
            else nextval[i] = nextval[j];
        }else{
            j = nextval[j];
        }
    }
}

串

# Ch4

# 模式匹配

# 暴力算法

# KMP 算法

ch3

ch2