学步园

在某个字符串中查找子串，这个编程题目看到过很多次了，一直没有动手做，只是零零散散的看了一些资料，没有做总结，这段时间刚好想到了，就对这个问题做个总结，先说说对KMP算法的理解。上面的参考资料1，对KMP算法描述的很清楚，但是没有具体的实现，参考资料2，这篇博文太长，感觉写的思路有点乱，作者想写得太全，对于KMP算法最关键的求解next数组的原理描述太少，资料三对KMP算法讲解得比较好，通俗易懂，推荐看资料三。

以在主串中查找字串为例，假设主串为S= "acabaabaabcacaabc"，子串（也称模式串）为P= "abaabcac"

基本字符串匹配算法

在某个字符串中查找字串，对于这样的字符串匹配，首先想到的就是最基本的算法：先让字串与主串的第一个字符比较，如果相等就比较主串与字串的第二个字符，如果不等就比较主串的第二个字符与子串的第一个字符，如果相等就比较主串的第三个字符和子串的第二个字符，如果不等，就比较主串的第3个字符与子串的第一个字符，......，如此下去，直到在主串中找到一个子串的匹配，或者主串结束。

下面为四趟匹配的示例：

第一趟：

第二趟：

第三趟：

第四趟：

这个中匹配算法比较直观，易于理解，但是效率比较低，时间复杂度为O(m*n)。可以看到在第三趟匹配到主串的第8个元素后，检查到子串最后一个字符与之不匹配，那么这趟匹配失败。然后，在第四趟匹配中，让子串的第一个字符再与主串的第四个字符匹配，但是主串的第四个字符与子串的第二个字符是匹配的，所以第四趟匹配肯定失败，这样的匹配方式就进行了不必要的匹配。

下面基本字符串匹配算法实现，时间复杂度为O(m*n)：

int str_match(char const *src, int slen, char const *pattern, int plen) {
	int i = 0, j =0;
	while(i < slen && j < plen)  {
		if(src[i] == pattern[j]){
			i++;
			j++;
		} else {
			i = i - j + 1;
			j = 0;
		}
	}

	if(i <= slen & j == plen)
	{
		return i - j;
	}
	else return -1;
}

KMP算法

int kmp_match(char const *src, int slen, char const *p, int plen, int next[]) {

	int i = 0,j = 0;
	while(i < slen && j < plen) {
		if(j == -1 || src[i] == p[j]) {
			++i;
			++j;
		} else {
			j = next[j];
		}
	}
	
	if(j >= plen){
		return i - j + 1;
	}
	return -1;

}

当i=1，j=1时匹配失败，此时查找next数组，next[1]=0，那么将子串右移一个字符，再进行第二趟比较；

第二趟：

S[1]与P[0]比较，此时匹配失败，那么j=next[0]=-1，由于此时主串S中的S[i]字符与子串的P[0]字符都不匹配，则指针i与j应同时右移1位（即加1）进行第三趟比较；

第三趟：

第三趟比较让S从S[2]开始与子串P进行比较，直到i=7，j=5时匹配失败，此时next[5]=2，那么将子串右移3（5-3）个字符位置使得S[7]与P[2]进行比较，即第四趟比较；

第四趟：

第四趟从S[7]与P[2]开始比较，直到P的最后一个字符与主串中的S[12]匹配，至此一次KMP匹配结束。

从两种匹配的示例可以看出，KMP算法明显比基本的匹配算法效率高（但是在某些情况下可能会低些，稍后再说），之所以效率高，是因为有了next数组，在字符匹配失败时，只要查找next数组就能知道下一次子串P中要参与匹配的字符的位置，那么next数组是怎么生成的呢？

假设主串S为's₁s₂s₃s₄......s_n'，子串P为‘p₁p₂p₃....p_m'，在字符匹配过程中假设主串S的i字符与子串的j字符匹配失败，那么此时应该选择子串P中的哪个字符与主串中的字符i比较呢？假设此时应该与子串中的第个k（k < j）字符比较，即S[i]与P[k]比较，那么子串的前k-1个字符必满足如下关系式子：

'p₁p₂.....p_k-1'='s_i-k+1s_i-k+2...s_i-1'

由于当前S中有部分字符与P[j]之前部分匹配，所以有如下关系式：

'p_j-k+1p_j-k+2.....p_j-1'='s_i-k+1s_i-k+2...s_i-1'

由上面两个式子推得：

'p₁p₂.....p_k-1'='p_j-k+1p_j-k+2.....p_j-1'

所以当S[i]与P[j]不匹配时就将子串P向右移动k个字符的位置，使得S[i]与P[k]比较，因为此时'p₁p₂.....p_k-1'与's_i-k+1s_i-k+2...s_i-1'是匹配的，相对于基本的匹配算法就省去了子串再从j=0开始匹配的过程（基本匹配算法中i向多移动了）。所以KMP算法的本质是在当前子串中匹配失败的字符前面的临近字符中找到几个相邻字符与子串的起始部分的几个相邻字符相匹配，如在KMP算法示例的第三步中，P[5]与S[7]匹配失败，那么在子串中找与P[5]之前的字符ab与子串起始的字符ab相同，那么此时就右移使得S[5]与P[0]对齐，S[6]与P[1]对齐。此时k应该是满足等式'p₁p₂.....p_k-1'='p_j-k+1p_j-k+2.....p_j-1'的最大k值（这一点与参考资料1这篇博文介绍的前缀后缀串相同），只有这样才能使得在KMP算法中每次移动的字符数最多，所以此时next[j]=k，对于next[0]，若主串中的字符S[i]与P[0]不匹配时，主串和子串同时往右移动一个字符，所以需要对于next[0]进行特殊处理，令next[0]=-1，此时next[0]=-1也方便编程实现。

由以上的分析可得出next函数的定义：

              -1,  j = 0

next =  k,    p₁.....p_k-1=p_j-k+1......p_j-1

             0,  其他

那么根据等式'p₁p₂.....p_k-1'='p_j-k+1p_j-k+2.....p_j-1'，从子串的起始字符开始找与'p_j-k+1p_j-k+2.....p_j-1'匹配的串，这又是一个字符匹配的问题。

假设next[j]=k，就有'p₁p₂.....p_k-1'='p_j-k+1p_j-k+2.....p_j-1'，对于next[j+1]就有两种情况：

1. p_k = p_j，所以'p₁p₂.....p_k-1p_k' = 'p_j-k+1p_j-k+2.....p_j-1p_j'，则next[j+1]=next[j] + 1;
2. p_k != p_j，所以'p₁p₂.....p_k-1p_k' != 'p_j-k+1p_j-k+2.....p_j-1p_j'，那么就要在从子串的起始字符处开始找到一个字符串'p₁p₂.....p_x-1p_x'，使得'p₁p₂.....p_x-1p_x'='p_j-x+1p_j-x+2.....p_j-1p_j'，其中x
   < k，而已经计算的next[k]=k₁表示当字符p[k]与主串（这里主串和字串是同一个字符串）不匹配时，下一次和p[j]的字符应该是第k₁，所以此时应该让p[k₁]与p[j]对齐，看是否匹配，若配匹配，即p[k₁]=p[j]，那么第j+1个字符之前存在一个长度为k₁的串和字串中从首字符起长度为k₁的字符串相等，则next[j+1]=k₁ + 1，如果不匹配，则继续比较p[j]与p[next[k₁]]，直到匹配或到字串的第0个字符。

/**
*p为字串，next数组为所要求的数组
*/
void get_next(char const *p, int next[]) {
	int i = 0, j = -1;
	next[0] = -1;
	while(p[i] != '\0') {
		if(j == -1 || p[i] == p[j]){
			++i;
			++j;
			next[i] = j;
		} else {
			j = next[j];
		}
	}

}

void get_next(const char *p, int next[]) {
    int len = strlen(p);
    int i = 0; 
    int j = -1;
    next[0] = -1;
    while(i < len) {
        if(j == -1 || p[i] == p[j]) {
            i++;
            j++;
            if(p[i] == p[j]) {
                next[i] = next[j];
            } else {
                next[i] = j;
            } 
        } else {
            j = next[j];
        }
    }
}