KMP模式匹配算法之 next[ ] 数组求值(天勤详解)

算法执行过程可以参考视频,看完了有个清晰的认知:

https://www.bilibili.com/video/BV1jb411V78H

代码如下:

字符串结构体

// 变长分配存储表示
typedef struct{
	char *ch;	 // 指向动态分配存储区首地址的字符指针
	int length;  // 串长度
}Str;

获取 next[ ] 数组值:

void getNext(Str subStr, int next[ ] ) {
    int i=1, j=0;  // 串从数组下标1位置开始存储,因此i 初始值为1,
    next[1] = 0;
    while(i < subStr.length) {
        if (j==0 || subStr.ch[i] == subStr.ch[j]) {
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];  // 回溯j值
        }

    }
}

配合下图,对代码的执行过程进行详解。

案例

假设有模式串 = “A  B  A  B  A  B  B  C  D  A  B  ”

其next[ ] 数组快速的计算结果,可以根据视频中的方法快速手算,如下:

分别用不同的颜色代表相应的字串与计算结果,此为快速计算next[ ] 的方法。

代码过程

根据KMP算法 next[ ] 数组的值,案例对着上面的代码运行过程如下:

注解:

代码中 if 条件
if (j == 0 || subStr.ch[i] == subStr.ch[j])
简记为  if 1  ||  2 : 
如果条件1成立记为 1√,条件2成立记为2√,不成立即为 x

1)根据不同的颜色可以看到next[ ] 赋值的来源 ;

2)回溯——根据程序,i 的值一直处于顺增,菱形标注了i 的值的变化;但是 j 的值在 if 条件不满足时,根据 j = next[j],进行回溯;如 Loop7的时候,j值为7,第一次回溯为3,第二次回溯为1,第三次回溯为0,然后if 条件满足,此时j增为1,保证了 next[i] 除了在初始化的特殊状态下为0,之后 next[ ] 的最小值也只能是1;

3)个人认为 next[ ] 的实际含义是当前字符位置在匹配串中有多少个字符已经匹配相同

搞清了next[ ] 的数值,下面来看如何在KMP主程序执行

KMP主程序

代码:

int KMP(Str str, Str substr, int next[]) {
	int i=1, j=1; // 串从数组下标1位置开始存储,因此初始值为1
	while(i <= sub.length && j <= subStr.length){
		if (j ==0 || str.ch[i] == subStr.ch[j]) {
			i++;
			j++;		
		}else {
			j = next[j]
		}
	}
	if (j > subStr.length) {
		return i - subStr.length;
	}else 
		return 0;
}

剖析:

1)仍然是通过 j = next[ j] 进行回溯的,仅仅是通过取出 next[ ] 里面的值;j 代表模式串和匹配串相同的字符集的个数;

2)i 确定位置,i - subStr.length 即可获取模式串在匹配串中的初始位置。

那么如上图求 next[ ],可以看到 j 在回溯的过程中,需要回溯多次计算跳跃值,存在重复计算已有值的情况,那么能不能让 j 只需要回溯一次就可以确定前面有多少个字符串匹配呢?这就是改进的KMP算法要做的事了。

注:本代码来源于天勤教材,具备科学性

喜欢就点左侧支持下吧?

原文地址:https://www.cnblogs.com/qianyuesheng/p/15405667.html