校招常考算法---KMP

    KMP算法是解决字符串匹配问题的也就是查看字符串A是否是字符串B的子串;那么我们常见的字符串匹配一般有  暴力匹配,朴素匹配,哈希匹配,KMP算法,

BM、sunday。当然这是按照时间复杂度排序的。如题目所示,我们今天学习的是KMP算法。

 

原理讲解:

    我们知道,暴力匹配和朴素匹配算法时间复杂度都是O(n*m),那么我们的KMP算法时间复杂度能降低到O(m+n),那么我们先看看暴力匹配的不足的地方,下面是我自己写的暴力匹配一段代码:

public int indexOf(String substr) {
		if(substr == null) return -1;
		for (int i = 0; i < mstr.length(); i++) {
			int k = 0;
			while(k < substr.length() && mstr.charAt(i) == substr.charAt(k) ) {
				k ++;
				i ++;
			}
			if( k == substr.length()) return i - k;
			else i-=k;
		}
		return -1;
	}

    我们可以看见,暴力算法的时间复杂度为O(nm),暴力算法每一轮匹配失败,直接回到匹配起点,从下一-点重新开始匹配,这样就造成了信息浪费。

   信息浪费:

         假设一轮匹配已经匹配了j个字符,在第j+ 1处失配”前j个字符可 进行匹配”这- -信息仍有应用价值,暴力算法中直接将这一 -信息丢弃

  如果你不懂什么叫做丢失已匹配信息,那么下面这张图可能会帮到你

图1:

算法详解---KMP(图1)

         KMP相对于暴力算法的优势就在于有效利用失配部分信息。那么如何利用呢?这就涉及到 前缀和后缀 的问题啦。其实说的通俗一点,就是在子串头尾找到最大长度的相同的串,用于下一次匹配的移动步幅。(说的不对请纠正)。那么我依然用一张图来表示:

图2:

        算法详解---KMP(图2)

上图我们可以看见的是,他连跳了两次,这是为什么呢?我们可以发现,在子串中,第一次失配的位置是4,那么我们观察 0-3(ABAB)四个字母,你会想到什么?没错,你肯定会想到是不是因为ABAB前面两个和后面两个是重复的,每次,你对了!当然,这是一个特殊的子串。但是这并不影响我们怎么去得到在失配前的子串的串最大的适配步幅。下面也用截图来计算一下 ABABABB 的步幅。

图3:

算法详解---KMP(图3)




   我们可以看见,上述的 ABAB 适配度为2,我们就相当于以4这个位置为中心,向后移动了两位,因为在4位置的前面,子串中最大的适配度是2,意思就是,子串首尾最多有两个字符是一模一样的序列,所以我们移动两位后,就可以保证在4的前面子串和原串可以匹配。

   你可能会问,那要是匹配度为0呢?是不是不移动?不!在匹配度为 1 或者为 0 的时候,我们都向后移动一位。那你的问题也许又来了,既然移动不多,那对时间能有多大的节约呢?也许在数据小的情况下,这两种算法之间根本拉不开差距,但是你要知道,如果在数以 百万计的巨大文本中去查找,差距就出来了。当然这也是我们生活中常见的。最直接的证明当然是我们的编译器。

   我们还可以看见,上述我们得到了一个数组,没错,这个数组就是我们的 next[ ] 数组。但是一般我们得到的这个数组不会直接使用,而是整体移动一位,比如上述数组整体向后移动一位变成 next[ 0 , 0 , 0 , 1  , 2 , 0 , 0],你虽然看见比上面多了一位,但是我们是从 1 开始使用这个数组,所以就相当于把他的下标整体移动了一位。(当然,往哪个方向移动,或者是不移动,取决于你自己,我们我们一直使用的只有 next[] 本身,只是为了后期代码的书写方便,如果你有能力,尽可随心);

   

代码实现:

   上面我们算是把,KMP算法原理讲完了,不知道你懂不懂,但是时间不等人,我们还是需要讲一下他的代码实现;

    首先我们先求出next[] 数组把,你可以想到,根据上面求适配度的过程写出代码似乎不太容易,那我们就可以换种思考方式,上诉中,我们依次在末尾添加字母,那么前缀和后缀似乎也是在最后添加一个相同的字母。很好,我们找到了一个相似点。可以通过第一个字符得到 next[] 数组,因为在代码中,我们第 0 个位置通常不使用,而第 1 个位置,因为只有一个字符,所以适配度也为 0 ,那么我们就以这两个位置为基础,计算出 next[] 数组。同样的,我们来一张图:

图4:

算法详解---KMP(图4)

    也许你可能会好奇,为什么单单在计算next[5]的时候,我们进行了回溯,而其他并没有,那是因为,next[4] != 0,当我们的next由前面叠加而来的时候,突然被中断,那么我们要去回溯一个点重新接上。很显然,这个例子并没有找到那个点。

    现在你想想,是不是用代码实现上述过程就比较容易多啦。

求next  代码

for (int i = 1; i < len; i++) {
	int j = next[i];
	while(j >0 && str.charAt(j) != str.charAt(i)) j =next[j];
	next[i+1] = str.charAt(j) == str.charAt(i)?j+1:0;
}

    看起来是不是很简单,五行代码就实现了,但是这对新手也许是不友好的,因为代码集成度比较高,所以就难以理解了;不过好在的是,这并不影响我们的思路。

    我们去循环了这个子串,很符合我们上述截图过程,我们让 j = next[i] ;下面这个 while 循环我们暂且忽略,第四行使用了一个三目运算符 ,我相信,这应该都知道。我们首先看看他的运算过程,判断子串中,str[i] 和 str[j] 是否相等,不知道你是否忘记,j = next[i] ;那么我们这句话就可以变为:

str.charAt(next[i]) == str.charAt(i)

   你会惊奇的发现,这和我们上面的图4一模一样,是的,当他们相等的时候,我们便把 j + 1 赋值给next[i +1],因为我们的 j = next[i];当他们不相等的时候,我们将next[i +1]赋值为0;

   不知道你有没有发现,有一点是不符合我们图4的,那就是当 next[i] != 0;的时候我们要进行回溯。如果你发现了,那么恭喜你,如果你没发现,那么这个功能正是while循环做的;


while(j >0 && str.charAt(j) != str.charAt(i)) j =next[j];

/*
 *因为 j = next[i] 所以我们循环条件也是 j >0 && str[ next[i] ] != str[i]
 *当我们回溯到 j = 0 的时候,我们让 j =next[j]; 而next[0] = 0,所以我们便没找到我们需要的节点
 *而我们的 str[ next[i] ] != str[i] 找不到相等时,便不停的回溯
 *
*/

  其实 j > 0 是为了防止回溯不到任何一个节点,所以最低让他回溯到 j = 0; 

  现在我想你应该很清楚,这段代码的意思了把,没错,他就是把我们图三完美呈现出来了;先定义一个辅助变量 j ,让他保留下我们的 next[i],然后先看看是不是需要回溯,如果不需要,一切正常进行,如果需要,那么我们再去比较第一个 也就是 j = next[j] ,回溯到需要的节点再进行判断。


KMP代码:

    上面都是KMP的辅助工具,那么下面我们来写出真正的KMP具体代码;

     根据图2,我们已经很清楚的知道怎么去匹配字符串了,因为我们已经会求步幅了(其实就是next[]),我们也能想到 KMP 并没有去移动原串的位置,而是不停的改变子串与原串的相对位置进行判断。

     ok,既然这样那么我们看看代码:

for (int i = 0; i < lens; i++) {
    while(j > 0 && strs.charAt(i) != str.charAt(j)) j =next[j];
	j = str.charAt(j) == strs.charAt(i)?j+1:0;
	if(j == len ) return i - len + 2;
}

   我的天哪,又是五行代码,别激动,他更有趣,同样的我们对原串做了一边循环

   我们看第二行和第三行代码,你会发现,咦,好像和我们求next[]是一样的,但你细心一些可能会发现,我们的 j 并不是初始为 next[i],而是 初始为 j = 0;而且我们在循环中并没有定义j ,j 是在循环外定义的,即(int j = 0;),那么这样有什么用呢?你看第四行代码就会明白,因为我们期望 j 能一直增长,直到和len(子串长度)相等的时候,即匹配成功!返回该子串第一次在原串中的位置。

   那么我们来解释一下第二行和第三行代码,同样的,我们这次是在原串(strs)中回溯,我们一直找到能匹配的节点,很显然,我们第一次循环( i = 0)时是肯定进入不了while循环的,因为此时 j = 0,那我们看第三行代码,判断当前str 与strs是否匹配,不匹配 j 依然等于 0,继续循环,直到找到与 str[0] 匹配的字符。

  如果找到了,那么我们现在j != 0,那么我们就可能进入while,如果一直能匹配,那很好,我们直到将str匹配完全退出循环都可以,如果匹配到一半,那么我们就又将进行回溯,直到找到我们能匹配那个 j 值,继续接着这个节点开始匹配。

  现在你可能会发现return i - len + 2 ;这一句我们似乎都没有讲,其实不讲你也能懂 i 是我们匹配完的最后那个位置,len是子串长度 但是为什么要加个2呢,我们的位置不应该是 i - len + 1吗?,对的,你想的没错,但是我们为了符合一般人思维,我们多加了一个1,表示下标从1开始。当然,根据需要,你也可以写出 i - len + 1;

  拓展一下,如果你想找到strs中有几个str应该怎么做?

   没错,我们只需要将 return i - len + 2 ;换成count ++;就可以啦,但是记住,我们的 j 也需要置零,不然的话,你懂的!

   好了,到此为止,我不清楚你到底有没有明白我所讲的一切,但是我想你多看几遍就能知道怎么回事,我把完整的代码贴在下面,自己拿去研究!

public int IsKMP(String strs,String str) {
		int lens = strs.length();
		int len = str.length();
		int[] next = new int[len + 1];
		next[0] = next[1] = 0;
		//查找子串
		for (int i = 1; i < len; i++) {
			int j = next[i];
			while(j >0 && str.charAt(j) != str.charAt(i)) j =next[j];
			next[i+1] = str.charAt(j) == str.charAt(i)?j+1:0;
		}
		for (int i = 0; i < next.length; i++) {
			System.out.print(next[i]+ " ");
		}
		//KMP算法  模式串匹配
		int j = 0;
		for (int i = 0; i < lens; i++) {
			while(j > 0 && (strs.charAt(i) != str.charAt(j))) j =next[j];
			j = str.charAt(j) == strs.charAt(i)?j+1:0;
			if(j == len ) return i - len + 2;
		}
		return -1;
	}

     算了,还是给你一个网站,这个题必须用KMP算法过,而且算是模板题快去试试你是否真的学会了吧。加油,奥力给!

感言:

    不瞒你说,这篇博客写了两个多小时,我不清楚这算长,还是短,但是我是真的用心,如果您感觉对你有所启发,我只希望你留下你的足迹(留言),便是我最大的安慰。