`

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

 

 

 

 

 

 

 

0
2
分享到:
评论
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又叫看毛片算法

相关推荐

    KMP算法,求子字符串位置

    KMP算法的核心是构建一个“部分匹配表”(也称为“失败指针”或“前缀函数”),它记录了子字符串的每一个前缀和后缀的最大公共长度。通过这个表,我们可以知道当子字符串的某个字符与主字符串中的字符不匹配时,...

    求两字符串的最长公共子字符串.docx

    标题中的“求两字符串的最长公共...总的来说,这个程序提供了一个基础的实现,展示了如何使用穷举法找出两个字符串的最长公共子字符串。对于大型字符串,应考虑使用更优化的算法,如动态规划的KMP或Z算法,以提高效率。

    KMP_字符串模式匹配算法

    部分匹配表通常用数组`lps`表示,其中`lps[i]`表示模式串中以第`i`个字符为结尾的最长公共前后缀的长度。对于每个位置`i`,我们可以通过检查模式串的前`i`个字符和前`lps[i-1]`个字符是否相同来更新`lps[i]`的值。 ...

    基于字符串模式匹配算法的病毒感染检测问题 实验四(源代码+实验报告)

    字符串模式匹配算法的主要目标是在一个大文本(主字符串)中查找是否存在一个或多个小的已知模式(子字符串)。这个过程中,有多种经典算法可以采用,例如: 1. **朴素匹配算法**:最基础的匹配方法,逐个字符比较...

    KMP.rar_KMP算法_字符串

    KMP算法,全称为Knuth-Morris-Pratt算法,是一种在字符串中寻找子串的高效算法,由三位计算机科学家Don Knuth、Vaughan Pratt和James H. Morris于1970年提出。该算法避免了在字符串匹配过程中不必要的回溯,极大地...

    KMP算法实现子串与多个主串的匹配

    在KMP算法中,我们主要关注两个字符串:模式串(子串,要寻找的字符串)和文本串(主串,要查找的字符串)。假设模式串为P,文本串为T,我们要找出模式串P在文本串T中所有出现的位置。 1. **构建部分匹配表**:这...

    易语言KMP算法模块

    该函数通过维护两个指针,分别指向目标字符串和模式串的当前比较位置,并结合部分匹配表来决定何时进行跳跃。 3. **字节集_子字节集寻找**:这可能是易语言提供的一个内置函数,用于在字节集中查找子字节集。在KMP...

    kmp.rar_kmp算法伪代码

    Hirschberg算法则是在线性时间复杂度内解决最长公共子序列问题的一种方法,也可以应用于字符串匹配。它通过分治策略将原问题分解为两个子问题,并通过动态规划来解决。Hirschberg算法的一个关键优势是避免了过多的...

    Kmp字符串模式匹配算法.doc

    从部分内容中可以看到,KMP字符串模式匹配算法的实现主要分为两个部分:makeNext和kmp。makeNext函数用于计算模式串的next数组,而kmp函数则用于实际的字符串匹配。 在makeNext函数中,next数组用于存储模式串的...

    kmp算法-基于C语言实现KMP算法.zip

    在这个例子中,我们首先定义了两个字符串`text`和`pattern`,然后调用`compute_Pi`函数生成部分匹配表,接着调用`KMP`函数执行匹配过程,并打印匹配次数。 五、KMP算法的效率分析 KMP算法的时间复杂度为O(m + n),...

    字符串处理算法

    Hash算法在字符串处理中常常被用来快速判断两个字符串是否相等,或者快速定位特定字符串的位置。在处理Hash冲突时,通常有开散列和闭散列两种策略。开散列通过在冲突位置建立链表来解决问题,而闭散列则通过移动到...

    字符串问题详解

    字符串相似度度量算法如Levenshtein距离提供了一种衡量两个字符串之间差异的方法,而最长回文串问题可通过Manacher算法高效解决。字符串匹配是解决许多实际问题的关键技术,它包括单模式匹配和多模式匹配两大类。 ...

    从头到尾彻底理解KMP算法

    它是一种用于在一维字符串(或数组)中查找子字符串(或模式)的算法。与朴素的字符串匹配方法相比,KMP算法具有更高的效率,其时间复杂度为O(n+m),其中n是文本字符串的长度,m是模式字符串的长度。 #### KMP算法...

    算法实现最长公共子序列问题(动态规划和KR算法)

    动态规划是解决LCS问题的常用手段,它通过构建一个二维数组来记录两个字符串的子序列长度。假设我们有两个字符串S1和S2,它们的长度分别为m和n,我们可以创建一个m+1行n+1列的矩阵L。对于每个位置(i, j),如果S1的前...

    字符串中的最长重复串

    最长重复子串是指在一个字符串中,连续重复出现次数最多的子串。解决这个问题通常需要使用滑动窗口、动态规划或者哈希表等数据结构和算法。下面将详细介绍几种常见的解决方案。 1. **滑动窗口方法**: 滑动窗口是...

    如何判断字符串的个数

    - 如果需要处理非连续重复子字符串的计数问题,可能需要采用其他算法(如 KMP 字符串搜索算法)。 总之,上述示例提供了一种简单有效的方法来计算一个子字符串在另一个字符串中出现的次数。这种方法适用于多种场景...

    字符串相关算法.rar

    例如,通过构造二维状态转移表,可以找出两个字符串的最长公共子序列。 6. **Trie(字典树)**:Trie是一种特殊的树形数据结构,用于高效地存储和检索字符串集合。通过将字符串的字符作为节点,可以快速进行前缀...

Global site tag (gtag.js) - Google Analytics