值得花费一周研究的算法 -- KMP算法(indexOf)
KMP算法是由三个科学家(kmp分别是他们名字的首字母)创造出来的一种字符串匹配算法.
所解决的问题:
求文本字符串text内寻找第一次出现字符串s的下标,若未出现返回-1。
例如
text : "adesceqwdasdfagf";
s : "sce";
return : 3;
常规解法 :
/**
* 常规算法
* 将以i为头的text子串与s串比对
* 如若比对失败则i++;继续比对i子串与s。
* @param text
* @param s
* @return
*/
public static int strStr(String text, String s) {
if (text == null || s == null || s.length() == 0 || text.length() < s.length()) {
return -1;
}
int i = 0, j = 0;
while (i + j < text.length() && j < s.length()) {
if (text.charAt(i + j) == s.charAt(j)) {
j++;
}else {
i++; j = 0;
}
}return j != s.length() ? -1 : i - j;
}
由于常规解法并不复杂并且,在注释上已经有概括讲解,所以我们就不再赘述了。
那么是否有更好一些的办法省去一些没有必要的操作以达到优化算法的目的呢？
以下是我们考虑的一个例子:
例如上图的例子,当前匹配的是以A开头的子串与s进行比对,而C,D不同,故而按照常规算法来说应该是i++,也就是i会到达B,j = 0,然后开始新一轮的比对,即TEXT中以B为头的子串与S进行再一次比对。
而这样的做法时间复杂度无疑是O(M*N); (M代表的是S的长度,N代表的是TEXT的长度);但是显然B和A的比较是无意义的,因为我们知道一个以B开头的子串是不可能与当前S串匹配的！
基于此我们推出升级版本的算法:
/**
* 升级版
* 猜想是否能有办法加速匹配速度
* 如若我第i + j 与 j未匹配上 即:text.charAt(i + j) != s.charAt(j)
* 是不是可以直接从i = i + j + 1 , j = 0继续匹配? 即 以头为i + j + 1下标为头的text子串与s串继续匹配
* 不一定可以!,但有时候一定可以,那么是在什么时候？
* 如若我s.charAt(0)与下标在[1, j]内的s串的字符都不相等,那么以[i + 1, i + j]为头的Text子串都不可能匹配上s,
* 因为text[i + 1, i + j]与s[1, j]一一对应,所以text[i + 1, i + j]都不与s.charAt(0)匹配
* 因为连第一个元素都匹配不上,怎么可能成功？
* 但如若[i + 1, i + j]内有等于第一个元素,那么就不能直接跳到i = i + j + 1了,为什么呢？
* 假若text.charAt(i + k) == s.charAt(0), k属于[i + 1, i + j]
* 因为第一个字符能匹配就意味着在text.charAt(i + k + 1) != s.charAt(1)...之后都是有可能的
* 如若跳过可能直接跳过了正确结论
* 那么基于以上结论我们可以做一个数组arr.
* 如若当前下标k和当前下标以前的节点没有第二个s.charAt(0)
* 则当前节点值为 arr[k] = -1;
* 如若有且下标为p 则将第一个标志出来
* arr[k] = p;
* 虽然这个升级版只对特殊s串有着显著的加速作用,但它对于我们进一步推至KMP是很关键的一个中间步骤
* @param text
* @param s
* @return
*/
public static int strStr1(String text, String s) {
if (text == null || s == null || s.length() > text.length()) {
return -1;
}
int[] help = getHelpArray(s);
int i = 0, j = 0;
while (i + j < text.length() && j < s.length()) {
if (text.charAt(i + j) == s.charAt(j)) {
j++;
}else {
if (help[j] == -1) {
i = i + j + 1; j = 0;
}else {
i = i + help[j] + 1; j = 1;
}
}
}return j != s.length() ? -1 : i - j;
}
public static int[] getHelpArray (String s) {
if (s == null || s.length() == 0) {
return null;
}
int[] res = new int[s.length()];
res[0] = -1; int first = -1;
for (int i = 1; i < res.length; i++) {
if (first == -1 && s.charAt(0) == s.charAt(i)) {
first = i;
}res[i] = first;
}return res;
}
基于以上结论 :
条件 ：当前以及匹配了j个元素,在第j+1个元素时不匹配
1)S[0,j-1]与text[i,i+j-1]一一匹配,那么我们可以通过这个容易忽略的性质加速算法。
2)如若S[1,j]都不等于S.charAt(0)其实我们是有办法利用1)性质来加速的
提出问题: 那么我们能不能做到一个更严格的筛选呢？ 例如我们能不能把以i + k为头的text子串如若存在text.charAt(i + k + e) != S.char.At(e);也给直接跳过了呢？ (k = 0是无意义的因为早就已经确认了,如若继续加入k = 0,则重复了S[0,j-1]与text[i,i+j-1]一一匹配，故: K > 0)
在这里e表示的是S串中第e个元素是否处在i+k为头的text子串正确的位置i + k + e上,如若不然，则i + k直接可以"淘汰"。
显然我们具备这个条件,只需要将text.charAt(i + k + e)找到之前与之对应的S串元素就可以在help数组内就"淘汰"它！
但显然我们有一个要求i + k + e < i + j 即 : k + e < j,因为只有在之前已经通过匹配的我们才知道他与S串的对应关系。
对于 e < j - K ：
j代表的含义是当前已匹配的长度,K是以i + K为头的text子串,也是以K为头的S子串（因为1)中的一一匹配性质）而e是以K为头的S子串所能匹配长度。
但是并非是e取最大的一个K子串就一定能确认他在j内是无法判断是否可以淘汰的,只要k + e < j,有一个字符无法匹配,那么我就一定能确认它要被淘汰,那么我就不用考虑i + k，而是考虑其他的。
如若S.charAt(k + e) != S.charAt(e)在e的取值范围e < j - K(此时K已选定)时都能成立,那么我就无法再不再次匹配时将他淘汰。其实这时候的S[0,e]与S[k,k+e]一一对应的关系有专业的名称，而我们推出的结论也就是著名的KMP算法:
首先在这里提出一个前缀串和后缀串的概念 : 前缀串简单来说就是在这个字符串下标包含[0,e]的一个子串,不过他得从0开始。与前缀串类似 后缀串是由 [k,j - 1]的一个子串,看到这是不是很眼熟？因为这就是我们之前所推的 S[0,e]与S[k,k+e]一一对应的关系,且因为如若e < j - k就会被淘汰,故而变成了S[0,e]与S[k,j - 1]。
另一个概念 : 最大相等前缀后缀长度。
例如 : ABAB 最大相等前缀后缀长度是2,如若取3，则前缀串为ABA后缀串为BAB，无法匹配。
AIJDWOA 最大相等前缀后缀长度是1
AAAA 最大相等前缀后缀长度是3，为什么不是4？ 因为要求K != 0,也就是说前缀串和后缀串不能是它本身,这点很重要。如若取他本身则在KMP中会发生无法避免的死循环。
为什么要提出最大相等前缀后缀长度这个概念？
因为S[0,e]与S[k,j - 1]一一匹配,如若有一个满足e最大 可以退出 k是最小符合条件的,那么就不会漏出未淘汰部分。而且最大相等前缀后缀长度其实就是e+1（e是下标从0开始数）.
举例说明 : 这里的i与上两个程序的i不同，不再是代表以i为头的子串的那个i，而是单纯的让i与j进行比较。
在上图S串中最大相等前缀后缀长度为2（U）,那么我们如若将j移动到2(U)(这里的2即是最大相等前缀后缀长度),而i不变就继续进行匹配,而且如若你举更多例子也仍然可以进行这种操作。这样的话我们就可以无论什么情况,都能达到i不后退！这就意味着我们的算法可能可以优化到了O(N)！
为什么是 j = U? 其实这就是说我们前面S.charAt[0,e]与S.charAt[K,K+e]与text.charAt[(i-j) + K,(i-j) + K+e]都一一对应了,i-j代表的是当前正以i-j开头的子串进行匹配。
既然我们已经知道了[0,e]都满足条件了,那么直接移动j至e+1比对即可！
但如若再次没比对成功呢？
如上图,如若j已经指向A，依然A!=C又该如何办呢？
这个问题看似复杂，但其实我们已经解决过了,这就是我们j指向D时候的问题嘛,前面都匹配,在j位置上时与i不匹配,那么上一次怎么解决的这次就怎么解决,唯一的不同就是U是这次对应的U，如若我们早已经把U放入help数组内，那么上一次是j = help[U];这一次仍然是。
那么如何求得我每次要的最大相等前缀后缀长度？
将这部分问题独立起来(求最大相等前缀后缀长度问题)并且简要概述:
有一字符串S，要求求出S每个下标index(依次为1,2,3,4...)前面index个字符组成的子串的最大相等前缀后缀长度并保存在数组内返回
public int[] getNextArray (char[] ch){ //这里使用char[]会比较方便
}
如若采取常规做法 : 这是很明显的O(M*M)
常规算法根本在于 从 i-1 开始猜测U并验证,直到找到真正的U
/**
* 判断每个字符的前缀最大对称 并且将数据组成数组返回
* @param str
* @return
*/
public static int[] makeNext(char[] ch) {
if (ch == null) {
return null;
}
int N = ch.length;
if (N == 1) {
return new int[]{-1};
}else if (N == 2) {
return new int[]{-1, 0};
}
int[] next = new int[ch.length];
//next[0]填入-1 而不是0 是为了标志这是0号元素 避免使用的时候发生死循环
//当然 你也可以直接在next[0]填入0 然后用下标识别
next[0] = -1; next[1] = 0;
for (int i = 2; i < N; i++) {
int res = i - 1, j = 0;
while (j < res) {
if (ch[i - res + j] == ch[j]) {
j++;
}else {
res--; j = 0;
}
}next[i] = res;
}
return next;
}
但是很幸运,我们有更好的方法来实现这个功能！
先贴代码后讲解:
public static int[] getNextArray (char[] ch) {
if (ch == null) {
return null;
}
int N = ch.length;
if (N == 1) {
return new int[]{-1};
}else if (N == 2) {
return new int[]{-1, 0};
}
int[] next = new int[ch.length];
next[0] = -1; next[1] = 0;
//这里的k在i++后其实就是next[i-1]但是有时候k与i-1没匹配上,意义就不再是这样了。
//在下面注释部分其实就是{}内语句的另一种形式 他们所起的作用是相等的
int k = 0, i = 2;
while (i < N) {
if (ch[k] == ch[i - 1]) {
next[i++] = ++k;
// k++;
// next[i] = k;
// i++;
}else if (k > 0) {
k = next[k];
}else {
next[i++] = 0;
// next[i] = 0;
// i++;
}
}return next;
}
采用这种做法的想法应该是: 我能不能找到某种next[i-1]与next[i]的联系来加速算法？
首先我们已知的是
S.charAt[0,next[i-1]-1]与S.charAt[(i-2)-next[i-1]-1,i-2]一一匹配
那么如若S.charAt(next[i-1]) == S.charAt(i-1)即可知道next[i] = next[i-1]+1;
为什么不能是next[i-1]+p,p属于[2,正无穷]
因为如若取得next[i-1] + p,那么就代表有
S.charAt[0,next[i-1] + p - 1]与S.charAt[(i-2)-next[i-1]-p+1,i-1]一一匹配
这里包含了一个信息即: [0, next[i-1] + p - 2] 与 [(i-2)-next[i-1]-p+1,i-2]是匹配的,而且next[i-1] + p - 2 > next[i-1]-1
那么next[i-1]就不是最大相等前缀后缀长度了。
那么如若S.charAt(next[i-1]) != S.charAt(i-1) 就要往回跳了
但是这个问题好像怎么这么熟悉？？？
字符串匹配算法？
对的,他还是字符串匹配算法,而且是已知help[0,i-1]的字符串匹配算法。当然,初学时候你或许不能很明白地看出来。
在这个图里我把下标i-1弄成了I,你就理解为 I = i - 1 吧..（非常抱歉,大家知道就好了..）。
在这里下面的代表的是S串,下面的代表着next串，并且两个串都具有help[0,i-1]根据之前我们得出的结论,即
如若 ch[k] == ch[i-1],这里的i-1就是之前的讨论KMP时的i，为待匹配元素下标,这里的k就是之前的j为匹配元素下标。
那么i++, j++; 但在这里就意味着next[i] = next[i-1] + i;也就是当前最大相等前缀后缀长度是前一个最大相等前缀后缀长度+1；
如若ch[k] != ch[i-1],那么 k = next[k]；也就是 j = U,在这里j就是k, U就存在netx[j]里面,也就是说 k = next[k]。
getNextArray();的另一种解释:
在图片示例中我们可以清楚的看到下标k的移动,k = next[k]就是说下一次与i进行比对的就是next[k]内元素,next[k]内元素即是以k为下标的前k个子串的最大相等前缀后缀长度.
那么为什么要这么跳？
这意思是一个下标对应的结果只能是[0,next[k]] U [k+1,k+1],这里k的初始值是next[i-1]。
这是一个有点递归感觉的区间,但显然[0,next[k]]中间并非是连续的整数,是否可取取决于数据情况。
证明 : 一个下标对应的结果只能是[0,next[k]] U [k+1,k+1]
为什么不能取到一个结果大于k+1?
在第一种解释就解释了！
为什么不能取到(next[k],k+1)的值？
如若取得这部分值,那么就代表e + 1变短了,或者取到了淘汰的值,那么就可能遗漏掉正确结论（讲最大相等前缀后缀长度之前讲过）。而next[k]是当前最"巧"值,比k+1大就就证明next[k]不是最大相等前缀后缀长度,取(next[k],k+1)就跳过头了,可能跳过正确结论,例如next[k]开头的子串就可能是结果。如若取< next[k]那就取到了已淘汰的值,浪费了之前辛辛苦苦求出来的next数据！
KMP算法:
/**
* KMP算法
* @param
* @param haystack
* @return
*/
public static int strStr2(String haystack, String needle) {
if (needle.length() > haystack.length()) {
return -1;
} else if (needle.length() == 0) {
return 0;
}
char[] ch1 = needle.toCharArray();
char[] ch2 = haystack.toCharArray();
// 获取next数组
int[] next = getNextArray(ch1);
int i = 0, j = 0;
// 比对
while (j < ch2.length && i < ch1.length) {
if (ch1[i] == ch2[j]) {
i++;
j++;
} else if (next[i] != -1) {
i = next[i];
} else {
j++;
}
}
return i == ch1.length ? j - i : -1;
}
其实KMP与getNextArray();是同一原理。在懂得了这一原理后,理解代码应该是比较容易的，所以我就不一一赘述了。
结尾是一些想法:
为什么KMP很难掌握而且又很容易忘记？因为这个算法确实是具有高难度的,思路十分精妙,尤其是getNextArray中再次将其提取为字符串匹配问题,且利用已有前i-1个元素的next求出第i个元素的next。是在令人惊叹。同样,这一部分代码也最为关键。不要以为它是一个辅助函数，其实它才是KMP的关键所在。所以一定要重视,多分析几次！
以下是简单证明,写的不算严格,但自己看了一遍觉得还是表达出了意思,这个证明有兴趣可以自己写个严格的,并且面试会考这个:
为什么是O(N)?
1)如若TEXT比S短 : 那么我们不可能再TEXT中找到一个子串等于S，return -1；
2)如若TEXT.length() >= S.length() :
有可能会有人觉得如果我S串极其特殊,且i指向的元素每次都不与j指向元素匹配呢？
例如 :
TEXT : ABABABABC...
012345678
S : ABABABABD
012345678
初始i = 8, j = 8; 第一次跳跃到j = 6,i不变,不匹配；第二次j = 4,不匹配；j = 2,不匹配那么这个长度就与M相关了,并且我仅仅需要隔着一段再出现这种数据就行了 若 TEXT : ABABABABCABABABABCABABABABCABABABABCABABABABCABABABABCABABABABCABABABABCABABABABC...
那么我不就很有可能就跌到了O(K*M*N)?
其实不会
1) 初始 J = 0 :
i) i,j不匹配.i++;
ii) i,j匹配,i++;j++;
2)J = K :
i)i,j不匹配,j往回跳K/X次数 （X>=1）
ii)i,j匹配, i++;j++;
在2)i)这里i,j不匹配往回跳K/X次数 (X>=1),但这里有一个很重要的前提即:J = K。 那么证明前K次是匹配的,这K次是N的一部分,那么对于这一部分来说就是(K-1) + K/X < 2K，就算全局都是之前举例的TEXT,那么 也只能是 N/K * ( K-1 + K/X ) < 2 * N。在这里K代表的是小于N,大于等于0的任意值,即使会有K1,K2,K3...每次K不一样,但K1 + K2 + K3...+ Kn = N一样是成立的,那么结果也会小于2*K1 + 2*K2 + 2*K3 +...+ 2*Kn = 2 * N;
所以无论多么极端的数据,也最大为2 * N;