彻底理解KMP算法

暴力匹配算法

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

• 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
• 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。 理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：

vector<int> ViolentMatch(char* s, char* p) {  
    vector<int> result;
    
    int sLen = strlen(s);  
    int pLen = strlen(p);  
  
    int i = 0;  
    int j = 0;  
    while (i < sLen) {  
        if (s[i] == p[j]) {
            //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++      
            i++;  
            j++;  
        }  
        else {  
            //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
            i = i - j + 1;  
            j = 0;  
        }
        if(j == pLen) {
            result.push_back(i - j);
            i = i - j + 1;  
            j = 0;
        }
    }
	return result;
}

KMP算法

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

• 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
• 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
  • 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j之前的字符串中有最大长度为k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。

转换成代码表示，则是：

 vector<int> KmpSearch(char* s, char* p) {
	vector<int> result;
	int i = 0;  
	int j = 0;  
	int sLen = strlen(s);  
	int pLen = strlen(p);  
	while (i < sLen ){  
		//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
		if (j == -1 || s[i] == p[j]){  
            		i++;  
            		j++;  
        	}  
        	else {  
            		//如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            		//next[j]即为j所对应的next值        
            		j = next[j];  
        	}
		if(j == pLen) {
            		result.push_back(i - j);
            		i = i - j + 1;  
            		j = 0;
        	}
    	}  
	return result;
}

步骤

• 1.寻找前缀后缀最长公共元素长度

  • 对于P = p0 p1 …pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 …pk-1 pk = pj- k pj-k+1…pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示：

    模式串|a|b|a|b
    —|—|—|—|—
    最大前缀后缀公共元素长度|0|0|1|2
    比如对于字符串aba来说，它有长度为1的相同前缀后缀a；而对于字符串abab来说，它有长度为2的相同前缀后缀ab（相同前缀后缀的长度为k + 1，k + 1 = 2）。

• 2.求next数组

  • next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第1步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第1步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：
    模式串|a|b|a|b
    —|—|—|—|—
    next数组|-1|0|0|1

• 3.根据next数组进行匹配

  • 匹配失配，j = next [j]，模式串向右移动的位数为：j - next[j]。换言之，当模式串的后缀pj-k pj-k+1, …, pj-1 跟文本串si-k si-k+1, …, si-1匹配成功，但pj 跟si匹配失败时，因为next[j] = k，相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀，即p0 p1 …pk-1 = pj-k pj-k+1…pj-1，故令j = next[j]，从而让模式串右移j - next[j] 位，使得模式串的前缀p0 p1, …, pk-1对应着文本串 si-k si-k+1, …, si-1，而后让pk 跟si 继续匹配。

综上，KMP的next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

通过代码递推计算next 数组

基于之前的理解，可知计算next 数组的方法可以采用递推：

• 1. 如果对于值k，已有p0 p1, …, pk-1 = pj-k pj-k+1, …, pj-1，相当于next[j] = k。
  • 究其本质，next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀。有了这个next 数组，在KMP匹配中，当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟文本串匹配，相当于模式串向右移动j - next[j] 位。
• 1. 已知next [0, …, j]，如何求出next [j + 1]呢？对于P的前j+1个序列字符：
  • 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
  • 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀”p0 p1, …, pk-1 pk”跟后缀“pj-k pj-k+1, …, pj-1 pj”相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, …, k, …, j]）进行P串前缀跟P串后缀的匹配。

综上，可以通过递推求得next 数组，代码如下所示：

void GetNext(char* p,int next[]) {  
    int pLen = strlen(p);  
        next[0] = -1;  
        int k = -1;  
        int j = 0;  
        while (j < pLen - 1) {  
            //p[k]表示前缀，p[j]表示后缀  
            if (k == -1 || p[j] == p[k]) {  
                    ++k;  
                    ++j;  
                    next[j] = k;  
            }  
            else {  
            k = next[k];  
            }  
        }  
}