算法系列之KMP算法

串的模式匹配算法
模式匹配是指将两个模式作为输入，计算模式元素之间语义上的对应关系的过程，在数据结构中模式匹配是字符串的基本运算之一。
有两个字符串S和T，字符串S称为正文（被匹配字符串），字符串T称为模式（匹配字符串），要求找出模式T在正文S中的首次出现的位置。一旦模式T在正文S中找到，就说发生一次匹配。
示例  目标 S : “Beijing”
         模式 T : “jin”
         匹配结果 = 3
首先来说说一般情况下的匹配模式：在字符串T跟字符串P上分别定义两个指针i，j，从0开始，如果S[i]==T[j]，i++；j++；指针下移，继续循环，一直到字符串T或者字符串P结束，如果匹配成功，返回i-j；如果中间出现S[i]!=T[j]，则i回溯（i=i-j+1）,而j也回溯（j=0）,继续循环。还是图比较好理解，见下图，从左到右（i=5-5+1=1，下图属于笔误，谢谢网友提醒）

代码如下（java实现）：

//------------串的模式匹配原声算法----------------
	public void index(char[] test,char[] pattern) {
		int test_len=test.length;
		int pattern_len=pattern.length;
		int i=0,j=0;
		while (i<test_len) {
			if (j==pattern_len) {
				System.out.println("配对成功：起始下标(从0开始)为---"+(i-j));
				break;
			}
			if (test[i]==pattern[j]) {
				i++;j++;
			}else {
				if (j==0) {
					i++;j++;
				}else {
					i=i-j+1;
					j=0;
				}
			}
		}
	}
	public static void main(String[] args) {
		char[] test="abcabcabdaaaaa".toCharArray();
		char[] pattern="abcabd".toCharArray();
		KMP kmp=new KMP();
		kmp.index(test, pattern);
	}

改进算法---KMP算法
百度百科：kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。
效果图如下：

至于j要回溯多少则关系到next函数值的求解：getNext()
       1.前两位必定为-1和0；
       2.计算第三位（下标为2）的时候，看第二位b的next值，为0，则把b和0下标对应的a进行比较，不同，则第三位a的next的值为0；
       3.计算第四位（下标为3）的时候，看第三位c的next值，为0，则把c和0下标对应的a进行比较，不同，则第三位a的next的值为0；
       4.计算第五位（下标为4）的时候，看第四位a的next值，为0，则把a和0下标对应的a进行比较，相同，则第五位b的next值为第四位a的next值加上1，为1，因为是在第四位实现了其next值对应的值与第五位相同。
       5.计算第六位（下标为5）的时候，看第五位b的next值，为1，则把b和1下标对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为2，因为是在第五位实现了其next值对应的值与第五位相同。
代码实现KMP算法：

package test.aglorith;
import java.util.Arrays;
public class KMP {
	//----------------KMP------------------------------
	public void indexByKMP(char[] test,char[] pattern) {
		int test_len=test.length;
		int pattern_len=pattern.length;
		int[] next=getNext(pattern);
		int i=0,j=0;
		while (i<test_len) {
			if (j==pattern_len) {
				System.out.println("配对成功：起始下标(从0开始)为---"+(i-j));
				break;
			}
			if (test[i]==pattern[j]) {
				i++;j++;
			}else {
				if (j==0) {
					i++;j++;
				}else {
					//i=i-j+1;
					j=next[j];
				}
			}
		}
	}
	public int[] getNext(char[] pattern) {
		int pattern_len=pattern.length;
		int[] next=new int[pattern_len];
		next[0]=-1;next[1]=0;
		for (int i = 2; i < pattern_len; i++) {
			int j=i;
			while(j>1) {
				if (pattern[i-1]==pattern[next[j-1]]) {
					next[i]=next[j-1]+1;
					break;
				}else {
					j=next[j-1];
				}
			}
			if (j==1) {
				next[i]=1;
			}
			//System.out.println(Arrays.toString(next));
		}
		System.out.println(Arrays.toString(next));
		return next;
	}
	public static void main(String[] args) {
		char[] test="abcabcabdaaaaa".toCharArray();
		char[] pattern="abcabd".toCharArray();
		KMP kmp=new KMP();
		kmp.getNext(pattern);
		kmp.indexByKMP(test, pattern);
	}
}

至于next函数值的求解原理至今还没有真正想透彻，希望广大网友多多指教！
经网友推荐的博客文章：http://www.cppblog.com/oosky/archive/2006/07/06/9486.html
突然缠绕我心中的那道弯就绕过了，之前在想:
求解T[i]时，T[i-1]与T[next[i-1]]不同时，T[i-1]要与T[next[next[i-1]]]比较；原因是一个词，“比较过了”。还是画图解释(不知道大家看不看得懂)：

评论

4 楼 edr_ 2013-09-27  

wwwcomy 写道

http://news.cnblogs.com/n/176771/

这个比较有帮助 图很好

嗯，讲得很详细！只是我没有具体说next函数值（部分匹配表）的算法。

3 楼 wwwcomy 2013-09-26  

http://news.cnblogs.com/n/176771/

这个比较有帮助 图很好

2 楼 edr_ 2013-09-26  

opqshuai 写道

i=5-5+1=0,错了，应该是1.

额，这个，笔误，画图太粗心了。谢谢啦！

1 楼 opqshuai 2013-09-26  

i=5-5+1=0,错了，应该是1.