从正文串S中查找目标串T,T也称为模式串。可以只查找一次,找到后立即返回第一次出现的位置,也可以查找全部出现的位置。
规定字符串匹配成功时返回第一个字符的下标,且下标从0开始,如果匹配失败则返回-1。
参考链接:
本篇只记录个人对KMP算法的总结,如果想从零基础开始学习KMP算法,建议看以上两篇讲解,或者参考其他写得更为详细的讲解。
BF算法
Brute Force,暴力算法,枚举S所有的子串,看与T串是否匹配,可以很容易地写出下面的代码:
int BF(string s, string t, int pos) { int i, j; int slen = s.length(); int tlen = t.length(); for(i = pos; i < slen - tlen + 1; i++) { for(int j = 0; j < tlen; j++) { if(s[i+j] != t[j]) { break; } } if(j == tlen) { // 匹配成功 return i; } } return -1; }
上面的匹配过程重点是i从s串从前往后移动,而j则是每次从t串的起始位置开始匹配,可以调整一下代码,将bf算法的代码写成下面这样的形式,以更加直观地看到代码中对于i和j的回退操作:
int BF2(string s, string t, int pos) { int i = pos; int j = 0; int slen = s.length(); int tlen = t.length(); while(i < slen && j < tlen) { if(s[i] == t[j]) { i++, j++; } else { i = i - j + 1; // i回退到上一轮开始比较的下一个字符 j = 0; // j回退到第一个字符 } } if(j == tlen) { return i - tlen; } else { return -1; } }
暴力匹配算法示意图如下:
KMP算法
针对暴力算法进行改进,改进的思路是如果S串和T串在位置j发生不匹配,则j之前的S串和T串是全部匹配的,可以通过一定的方法省去一些匹配步骤,不需要让j再从头开始匹配。
KMP算法的具体操作:计算出T串在位置j处的最大公共前后缀,如果在j处发生不匹配,则将j之前的最大公共前缀直接挪到最大公共后缀的位置,从而省去对最大公共前缀的比较,如下:
上面的操作其实等价于在j位置发生不匹配时,i保持不动,j回退到最大公共前缀的后一位继续比较。由于i不回退,所以KMP算法在比较S串和T串时的时间复杂度为O(n)级别,其中n为S串的长度。
由于在任何位置都有可能发生不匹配,所以需要计算出T串在每个位置的最大公共前后缀长度,这也是KMP算法的重点,记T串在位置j处的最大公共前后缀长度为next[j]
,则next[j]
的值可以分为以下两种情况:
- j等于0,此时j指向T串的首字符,j之前不存在字符串,也就不存在最大公共前后缀,这里可以将next[j]设置为-1,以表示next[j]不存在。(实际上设置成其他负值也可以,但设置成-1可以方便计算,以便统一代码形式,这点请参考get_next()函数进行理解。)
- j不等于0,此时j前面存在字符串,也就存在最大公共前后缀,next[j]表示j前面的字符串的最大公共前后缀长度,注意,next[j]可以为0,表示j前面的字符串最大公共前后缀长度为0。典型地,当j等于1时,j前面的字符串长度为1,由于前后缀不能包含字符串本身,所以next[1]的值必然为0。
关于next[j]的计算代码如下:
int slen, tlen, next[10000+5]; void get_next(string t) { next[0] = -1; int j = 0, k = -1; while(j < tlen) { if(k == -1 || t[j] == t[k]) { next[++j] = ++k; } else { k = next[k]; } } }
假设next[j]=k,则以上代码对应的示意图如下:
这里重点需要理解的是在t[j]与t[k]不相等时,k回退到next[k]的操作,也就是k=next[k]
。
计算出next数组后,整个KMP算法的实现如下:
int KMP(string s, string t, int pos) { int i = pos; int j = 0; slen = s.length(); tlen = t.length(); get_next(t); while(i < slen && j < tlen) { if(j == -1 || s[i] == t[j]) { i++, j++; } else { j = next[j]; } } if( j == tlen) { return i - tlen; } else { return -1; } }
到此已经可以解决28. 实现 strStr() - 力扣(LeetCode)这个问题。
KMP算法优化
当t[k]=t[j]时,原则上next[j+1]=k+1,但当t[j+1]=t[k+1]时,回退到k+1没有意义,因为s[i+1]与t[j+1]是不相等的,那么s[i+1]与t[k+1]也必然不相等,所以这次回退可以直接判定不匹配,这时,应该让next[j+1]再回退一次,回到next[k+1],从而减少一次不必要的比较。
只需要改进next数组的计算方法,KMP算法的主体不需要调整,改进后的算法如下,为了区别前面的版本,这里将函数命名为get_nextval(),将计算结果存到nextval数组中:
int slen, tlen, nextval[10000+5]; void get_nextval(string t) { nextval[0] = -1; int j = 0, k = -1; while(j < tlen) { if(k == -1 || t[j] == t[k]) { j++, k++; if(j < tlen && t[j] == t[k]) { nextval[j] = nextval[k]; } else { nextval[j] = k; } } else { k = nextval[k]; } } }
这里不需要考虑要不要多次回退的问题,因为get_nextval()是从前往后处理的,如果回退位置上有多个相同的字符,则get_nextval()在处理时,会先让第一个字符回退到底,然后后面的字符依次继承前面的回退位置,也就是后面的相同字符全部都是一次回退到底,不需要多次回退,这里贴一个get_next()和get_nextval()计算结果的对比,对比一下结果就知道了:
这里通过get_nextval计算出来的e的回退位置全部是0,效果就是不管在哪个位置不匹配,都可以一次回退到底,不需要多次回退。
KMP算法复杂度
假设S串和T串的长度分别为n,m,则KMP算法的算法复杂度为O(n+m),因为S串和T串都只需要扫描一遍。
- 无标签