基于KMP算法求两个字符串的最大公共子字符串

在维基百科中对这个算法的介绍是：

“在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（常简称为 “KMP算法”）可在一个主“文本字符串” S 内查找一个“词” W 的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

这个算法是由高德纳（Donald Ervin Knuth）和 沃恩·普拉特 在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终由三人于1977年联合发表。”

?基于这个算法，当我们来描述求解两个字符串包含的最大公共子字符串。我们将较长的字符串作为主字符串（L）,较短的字符串为匹配字符串（S）

? ?用L[m]与S[0]比较，如果L[m]!=S[0],在用L[m]与S[1]比较，如果L[m]!=S[1],再用L[m]与S[2]比较。直到匹配到L[m]==S[n],然后再用L[m+1]于S[n+1]比较，如果L[m+1]==S[n+1]，在用L[m+2]与S[n+2]比较。直到匹配到L[m+x]!=S[n+x]或者length(L)==m+x||length(S)==n+x(达到边界，即两个字符串有一个匹配到了结尾)。那么这时我们匹配到L与S的一个长度为x的公共子字符串。然后继续用L[m]与S[n+1]比较。

重复上述的步骤，直到L匹配到边界。实现如下：

?

??

public String getLargestPatch(char[] longerStrArray,char[] shorterStrArray){
		int startIndex=0;
		int endIndex=0;
		int tmpStartIndex=0;
		for(int i=0;i<longerStrArray.length;i++){
			int x=i;
			if(i==9){
				System.out.println();
			}
			for(int j=0;j<shorterStrArray.length&x<longerStrArray.length;j++,x++){
				if(longerStrArray[x]==shorterStrArray[j]){
					int m=x;int n=j;
					tmpStartIndex=m;
					for(;m<longerStrArray.length&&n<shorterStrArray.length;m++,n++){
						if(((m+1)==longerStrArray.length||(n+1)==shorterStrArray.length)||longerStrArray[m]!=shorterStrArray[n]){
							if(m-tmpStartIndex>endIndex-startIndex){
								startIndex=tmpStartIndex;
								endIndex=m;
							}
							break;
						}
					}
				}
				
			}
		}
		return new String(longerStrArray,startIndex,endIndex-startIndex+1);
	}

?

?

?

?

?

?

?

基于KMP算法求两个字符串的最大公共子字符串

原文：http://zfh521.iteye.com/blog/2153241