串模式匹配

Content

• 串的模式匹配
• BF算法
• KMP算法

串的模式匹配

概念：在主串中找到与模式串相同的子串，返回其所在位置

BF算法

O(n^2)暴力扫描，思路简单

int BF(const string& S, const string& T){
    auto m = S.length(), n = T.length();           // 长度
    auto index1 = 0, index2 = 0;
    while(index1 < m && index2 < n){
        if(S[index1] == T[index2]){
            ++index1;
            ++index2;
        }else{                                                              // 比较失败，从S上次起始的下一个字母开始匹配，T回到第一个
            index1 = index1-index2+1;
            index2 = 0;
        }
    }
    if(index2 == n)  return index1 - n;
    return -1;
}

KMP算法

思想：当两个字符失配时，可以得到信息：前面的所有字符都匹配成功。KMP算法就是利用这部分信息，让i不回溯，提高匹配效率

KMP算法具体解释，可以移步我的BiliBili视频 手撕KMP！｜理论+cpp实现

下面给出王道考研书的实现：字符串从数组的下标1处开始

求next数组—手动

1. next[1] = 0
2. 字符i的前缀：区间[1, i-1)范围内，必定包含[1]位置处字符的子串
3. 字符i的后缀：区间(1, i-1]范围内，必定包含[i-1]位置处字符的子串
4. next[i] = 字符i处，最大相等前后缀长度+1

求next数组—计算机

相当于模式串和自己KMP

void get_next(const String& T, int next[]){
    int i = 1, j = 0;
    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];
        }
    }
}

KMP算法—index从1开始

int KMP(const String& S, const String& T, const int next[]){
    // i扫描文本串S，j扫描模式串T
    int i=1, j=1;
    while(i <= S.length && j <= T.length){
        if(j == 0 || S.ch[i] == T.ch[j]){
            ++i;
            ++j;
        }else{
            j = next[j];
        }
    }
    // 如果j扫描完T，说明匹配成功
    if(j > T.length)    return i-T.length;
    // 失败返回0
    return 0;
}

nextval数组—KMP算法优化

可以减少不必要的比较

• 手动计算：

1. nextval[1] = 0 定义
2. 从左往右推。求出next[j]， 如果S[j] = S[next[j]]，则nextval[j] = nextval[nextval[j]]；反之nextval[j] = next[j]

• 算法实现

void get_nextval(const String& 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];
        }
    }
}

KMP匹配过程则和原本一样

赏

谢谢你请我吃糖果

支付宝

微信