第四章 串的匹配模式

基础概念

相关提炼内容见 string。

• 简单的模式匹配算法——BF 算法

int Index_BF(SString S, SString T, int pos) {
int i = pos, j = 1;
while (i <= S.length && j <= T.length) {
if (S.ch[i] == T.ch[j]) {// 比较成功则继续匹配下一个字符串
    i++;
    j++;
}
else { // 比较不成功则回溯
    i = i - j + 2;
    j++;
}
}
if (j > T.length)  return  i - T.length;  // 看下文注释
else return 0;
}
 
/*
j >= T.length 是错误的，举个反例：
S = {"abcdef"}; T = {"fg"}
when i = 6;
S.ch[i] = T.ch[j] = 'f';
Then i=7; j=2;
此时不符合循环条件跳出。明显j = 2匹配成功了
*/
 

• 改进的模式匹配算法——KMP 算法
  • 主函数

int Index_KMP(SString S, SString T, int pos) {
int i = pos, j = 1;
while (i <= S.length && j <= T.length) {
if (j == 0 || S.ch[i] == T.ch[j]) { // j == 0或者比较成功则继续匹配下一个字符串
    i++;
    j++;
}
else
    j = next[j] // 比较不成功则回溯
}
if (j > T.length)  return  i - T.length;  // 看下文注释
else return 0;
}

- 获得next函数

void Get_next(SString T, int nextval[]){
int i = 1, j = 0;
nextval[1] = 0;
while (i < strlen(T)) {
if (j == 0 || T.ch[i] == T.ch[j]) next[++i] = ++j;
    else next[i] = next[j];
else j = next[j]; // 隐含着非常厉害的递归思想
}
return 0;
}

- 时间复杂度$O(m+n)$ ，其中$O(m)$ 来自于求next数组，$O(n)$ 来自KMP算法的里层循环（普通模式匹配算法的时间复杂度是$O(mn)$

• KMP 算法的进一步优化
  • 获得 nextval 函数

void Get_next(SString T, int nextval[]){
int i = 1, j = 0;
nextval[1] = 0;
while (i < strlen(T)) {
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]; // 隐含着非常厉害的递归思想
}
return 0;
}