基于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);
	}

 

 

 

 

 

 

 

评论

4 楼 zfh521 2014-11-07  

cywhoyi 写道

zfh521 写道

cywhoyi 写道

KMP又叫看毛片算法

高人，看毛片都能看出算法来！

记得那时给大家分享KMP算法时，用google拼音，打出来KMP，联想到看毛片，那个囧。
回归算法本身，希望能够帮助到你
1.KMP算法最重要的是KMP TABLE，即next函数，在code中一丁点都未发现
2.KMP算法是解决回溯问题，本身哪怕是贪心算法也就，O(N*N)，你的代码是O(N*N*N),KMP是O(M+N),你这段代码有问题吧

KMP算法是在在句子中查找单词的位置，本例借用了KMP算法的思想。不知道是不是用错了！

3 楼 cywhoyi 2014-11-07  

zfh521 写道

cywhoyi 写道

KMP又叫看毛片算法

高人，看毛片都能看出算法来！

记得那时给大家分享KMP算法时，用google拼音，打出来KMP，联想到看毛片，那个囧。
回归算法本身，希望能够帮助到你
1.KMP算法最重要的是KMP TABLE，即next函数，在code中一丁点都未发现
2.KMP算法是解决回溯问题，本身哪怕是贪心算法也就，O(N*N)，你的代码是O(N*N*N),KMP是O(M+N),你这段代码有问题吧

2 楼 zfh521 2014-11-07  

cywhoyi 写道

KMP又叫看毛片算法

高人，看毛片都能看出算法来！

1 楼 cywhoyi 2014-11-07  

KMP又叫看毛片算法