KMP算法

前言

之前也看过KMP算法，但是看不懂呀。
现在，终于搞懂啦！

导读：

前言
概述
必备知识
KMP讲解
题目举例

概述

首先我们来看一下KMP要解决的问题：
有2个字符串str和match。让你判断在str里是否有子串match，如果有放回这个子串在str里的开始位置，，如果没有，则返回-1。
（str长度为N，match长度为M； N >= M，否则没有子串这个概念）
比如：
str ：x y a b a b a f w y 　　　　　match：a b a b a f ；　返回 2。
str ：x y a b c d e　　　　　　match ：a b a b a f ；　返回-1。

先来看下普通解法：
从str里的第1个位置的字符开始，和match匹配，相等，都往下移一个位置，再匹配；不相等，从str的下一个位置开始，match从头匹配。这样一步步的暴力解决。
所以最坏情况下，str的每个位置都要开始，有N个位置；每次都要匹配match的最长长度，有M个位置。所以时间复杂度为 O(N*M)

而，KMP的时间复杂度可以做到O(N)。也就是算最多遍历一遍str就可以求解！
下面就来看下具体是怎么操作的。

必备知识

在KMP中，有一个很重要的概念，叫某个字符的最长前缀和和最长后缀。就是利用这个信息来加速整个过程的。（可以说如果这概念不懂的话，是理解不了KMP算法的。）
用next数组来存储match字符串的前缀和后缀相等的 最长长度 这个信息。

先用 ababaf 字符串来举例说明一下：

规定: 前缀的不能包含最后一个字符，后缀的不能包含第一个字符，否则前缀和
　　　后缀都是之前的这个完整字符串，最长肯定是它，那我们求这个信息还
　　　有什么意义呢…
还有：
规定: 第一个字符的next值为-1，因为它之前没有字符串；
　　　第二个字符的next的值为0，因为它之前只有一个字符，还不是前缀或后缀字符。
　　　
至此，next数组的概念就介绍完了，下面来看看怎么求这个next数组信息。

就是从头开始遍历过来，
假设求到第i个位置，之前的位置的next的值我们都已经知道了。
找到我们求的字符的前一个字符（第i-1个字符）是什么，在看他的next值，就是看第i-1个字符的最长前缀的下一个字符是什么（假设这个字符所在的位置为j），再和他自己比较，
相等的话，则第i个位置的next值就是第i-1个位置的next值加一得到。
不相等的话，在看第j个位置的next值，就是看第j个字符的最长前缀的下一个字符是什么，再和第i-1个字符比较。相等，则第j个位置的next值加一得到
　　　　　　　　　　　　　不相等，则重复此步骤。

举个例子，比如字符串： a b a b c a b a b a k ：
为什么可以这样呢，画个示意图说明下，画的丑。能看懂最好，看不懂就…算了吧…

好了，next数组算是搞定了，下面是求next数组的代码实现：

	public static int[] getNextArray(char[] m) {
   
		if(m == null || m.length == 1) {
   
			return new int[] {
   -1};
		}
		
		int[] next = new int[m.length];
		next[0] = -1;
		next[1] = 0;
		int count = 0;	// 记录 当前的最长前缀 和 最长后缀 的长度是多少，也就是那个next值
		int i = 2;
		
		while( i < m.length) {
   
			if(m[i-1] == m[count]) {
   
				count = count + 1 ;	// 因为相等了，所以数量+1
				next[i] = count;
				i++;
			} else if (count > 0) {
   
				count = next[count];
			} else {
   
				next[i] = 0;
				i++;
			} 
		}
		
		return next; 
	}

KMP

好了，下面就是要实现KMP这个过程了！
假设我们现在一直从str字符匹配过来，匹配到match的第i个位置，与str的不匹配了。到这里，next的值就派上用场了！
看看match的第i个位置的字符的next值是多少，也就是看match的第i个位置的字符的最长前缀长度是多少，next的值代表这个最长前缀的下一个字符（假设为第j个位置）。将现在str的位置的字符与 match上的第j个位置的字符比较。
相等的话，接着比较下面的字符；
不等的话，就接着重复此步骤，知道match字符串指到了第一个字符，就又从头开始了。

这里也是画个示意图说明下…
举个例子： str ： a b k a b a b k a b D
　　　 match ： a b k a b a b k a b F
匹配到D和F的时候不等了，接下来的匹配过程如下图：

好了，至此，KMP的算法就完了，感觉就是next数组是他的核心内容。
他的时间复杂的是求一遍next数组（为O(M)）加上
　　　　　　　遍历一遍字符串str（为O(N)）
所以总的时间复杂度为O(N)。　　
　　　　
上代码实现：

	public static int getIndexOf(String str, String match) {
   
		if(str == null || match == null) {
   
			return -1;
		}
		
		char[] s = str.toCharArray();
		char[] m = match.toCharArray();
		int[] next = getNextArray(m);
		int si = 0;		// 在str字符串中用的 位置指标记号
		int mi = 0;		// 在match字符串中用的 位置指标记号
		
		while(si < s.length && mi < m.length) {
   
			if(s[si] == m[mi]) {
   
				si++;
				mi++;
			} else  {
   	// 不相等时
				if(next[mi] == -1) {
     // match中来到第一个字符了
					si++;
				} else {
   		// match中的next值还可以跳时
					mi = next[mi];
				}
			} 
		} 
		
		return mi == m.length ? si-mi : -1;
	}

题目：

来看道题看看怎么用这个算法：

题目：

给你一个字符串，在他后面添加另一个字符串，得到一个新的字符串。
要求新的字符串包含原本的字符串两次，而且这个添加的字符串是要长度最短的，或者说新的字符串在所有可能的结果里要长度最短，返回这个新的字符串。
比如：一个字符串： a b c a b
可以添加原本的字符串，得到： abcab abcab，包含原本字符串两次
也可以添加　　 abc，得到： abcababc，　　包含原本字符串两次
但是，后者的字符串最短，返回这个字符串。

思路：

主要用到的是KMP算法的变形，也是求这个字符串的next数组，只不过这个next数组要长度要多一位，我们要的是最后一位的next值，也就是这个字符串的最后一个字符的后一位的next值。
这样就知道了这整个字符的相等的最长前缀和最长后缀是多少，
添加的是这整个字符从不要最长前缀，要最长前缀之后的字符。即可得到答案。