欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KMP 深入理解next数组

程序员文章站 2024-02-16 09:22:34
...

一、引言

  • KMP又称模式匹配算法,能够在线性时间内判定字符串A[1~N]是是否为B[1 ~ M]的子串,并求出A在B中各次出现的位置。

二、基本含义

  • next数组:next[i] 代表A中以i结尾的非前缀子串(非前缀子串的意思就是不能和A完全相等的后缀子串) 与 A的前缀能够匹配的最大长度。
  • 当不存在这样的前缀串时,显然next[i] = 0, 故next[1] = 0 (因为第一个字符前面没有字符串且第一个字符不是非前缀子串)
  • 我们可以让A对B进行匹配,求出一个数组p。p[i]代表以i结尾的子串 与 A的前缀能够匹配的最大长度。 当p[i] = n(A的长度)代表匹配此位置成功。

三、next数组的求解

1. 朴素的求解next数组

  • 假定A串为 abababbc
    KMP 深入理解next数组

2. 优化求解next数组过程

KMP 深入理解next数组

void getNext() { //n串A串的长度
 for (int i = 2, j = 0; i <= n; i++) { //求解next[i] 
 	while (j && A[i] != A[j + 1]) j = ne[j]; //这时候找到一个符合的位置 A[i] == A[j + 1] 那么就停止了。
 	if (A[i] == A[j + 1]) j++; //这时候有2种情况,j==0:代表前面的串都不满足。 否则那么next[i] = j + 1。
 	ne[i] = j; // 求解出ne[i] 。  
 }
}

三、kmp算法

  • 这时候我们与串B匹配的过程和求解next的过程大同小异。
void kmp() {
	for (int i = 1, j = 0; i <= m; i++) {
		while (j && B[i] != A[j + 1]) j = ne[j]; 
		if (B[i] == A[j + 1]) j++; //在前面已经匹配的长度的基础上加1
		p[i] = j; //代表B串以i结尾的子串与 A的前缀的最大匹配长度 匹配串为B[i - j + 1, i]
		//if (j == n) {//匹配成功 }
	}
}

四、其他应用

  • 最小循环节
    KMP 深入理解next数组
相关标签: 算法 kmp