`
raojl
  • 浏览: 208847 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求最大公共子串

 
阅读更多
#include <stdio.h>
#include <stdlib.h>
#include <string>

using namespace std;

struct stringtag
{
	string value;
	int tag;
};

int stringcompare(const void* A,const void* B)
{
	struct stringtag* AA = (struct stringtag*)A;
	struct stringtag* BB = (struct stringtag*)B;
	return (*AA).value.compare( (*BB).value);
}

int cutstring(struct stringtag strarr[],int arrsize,string sourcestr,int tag)
{
	int i = 0;
	for(; i < arrsize && i < sourcestr.length(); i ++){
		strarr[i].tag = tag;
		strarr[i].value = sourcestr.substr(i);
	}
	return i;
}
int getmatchstr(struct stringtag A,struct stringtag B)
{
	int i = 0;
	for(; i < A.value.length() && i < B.value.length();i ++)
		if(A.value.c_str()[i] != B.value.c_str()[i]) break;
	return i;
}

int main(int argc,char* argv[])
{
	string testa = "awerdasadfdfdfqedfjhoqewhjkhadsf";
	string testb = "weqwdadfefdzxcverqrjhr";
	struct stringtag aArr[100] = {""};

	int len = cutstring(aArr,100,testa,0);
	len = cutstring(aArr+len,100 -len,testb,1) + len;
	qsort(aArr,len,sizeof(struct stringtag),stringcompare);
	int matchlen = 0,maxindex = 0;

	for(int i = 0; i < len -1; i ++ )
	{
		if(aArr[i].tag != aArr[i+1].tag)
		{
			int tmplen = getmatchstr(aArr[i],aArr[i+1]);
			if(tmplen > matchlen) 
			{
				matchlen = tmplen;
				maxindex = i;
			}
		}
	}
	printf("max common substr:%s \n",aArr[maxindex].value.substr(0,matchlen).c_str());
	return 0;
}

 

分享到:
评论

相关推荐

    求最大公共子串.cpp

    求最大公共子串 s1和s2最长公共子串 c/c++源代码

    JavaScript实现求最大公共子串的方法

    标题中的"JavaScript实现求最大公共子串的方法"指的是在JavaScript编程语言中寻找两个字符串共有的最长子串。这个任务在计算机科学中属于字符串处理的一部分,常用于文本分析、比较和搜索算法。 描述中提到的...

    求N个字符串的最大公共子串

    求最长的公共子串 求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长...

    求最长的公共子串

    两个字符串里求最长的公共子串

    最大公共子串计算论文相似度源程序

    最大公共子串计算论文相似度:事件复杂度O(m*n),空间复杂度Omin(m,n)),可以用来计算两个字符串的最大公共子串长度、相似度;可以用于论文相似度量、地理信息等基于相似度量的查询等环境。由于空间复杂度低,因此可...

    动态规划实现两序列最大公共子串查找(Python代码)

    最大公共子串问题是IT行业的经典面试题之一,在生物信息等领域也有重要应用。该资源使用动态规划实现了最大公共子串查找算法,问题具体描述在Problem里,代码为code.py,调试结果请参考Readme。

    C++实现找出两个字符串中最大的公共子串

    本主题将深入探讨如何使用C++语言来实现一个算法,该算法能够找出两个字符串中的最大公共子串。公共子串是指同时存在于两个或多个字符串中的任意非空字符序列。在本问题中,我们目标是找到最长的这样一个子串。 ...

    动态规划求最大匹配子串

    动态规划求最大匹配子串是计算机科学中的一种常见问题,旨在寻找两个字符串之间的最长公共子串。这种问题可以使用动态规划算法来解决,下面我们将详细介绍该算法的思想和实现。 算法思想: 假设我们有两个字符串...

    LCS(longest common substring)算法,即最大公共子串 C实现

    LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...

    N个字符的 最大公共子串的长度

    求N个字符的最大公共子串的长度 从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下的字符按原来顺序组成的串是该串的子串。例如: “”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是...

    java实现字符串匹配求两个字符串的最大公共子串

    在Java编程中,实现字符串匹配并...总之,Java实现字符串匹配求两个字符串的最大公共子串是一个涉及字符串处理和动态规划的经典问题。通过理解上述算法思想和代码实现,开发者可以有效地处理文本数据的比较和分析任务。

    C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...

    最长公共子串MFC实现

    最后,最长公共子串的长度就是dp数组的最大值,而子串本身可以通过回溯dp数组得到。 在MFC项目中,我们可以将这些算法逻辑封装到一个类中,比如CLCSAlgorithm,该类包含计算LCS的方法,并可能有一个成员变量来存储...

    最大公共资源子串

    本文将详细介绍如何利用C语言实现最大公共子串(Longest Common Substring,简称 LCS)的计算方法。最大公共子串问题是指在两个或多个字符串中找到最长的相同子串。本算法采用动态规划的方式解决这一问题,并通过一...

    <华为OJ>公共子串计算

    公共子串计算,输入两个字符串,忽略大小写,输出公共子串的最大长度

    PHP实现求两个字符串最长公共子串的方法示例

    这样,数组$c$的每个元素就存储了对应位置的最大公共子串长度。 在循环结束后,我们遍历数组$c$找到最大值,并且找出对应的子串。我们使用`substr()`函数从字符串$b$中提取出最长公共子串,因为数组$c$是根据字符串...

    新建 WinRAR 压缩文件_最长公共子串_

    最后,遍历完成后,dp数组中的最大值即为最长公共子串的长度。 在C++实现中,我们通常会创建一个函数,如`longestCommonSubstring(const string &s, const string &t)`,并在这个函数内部构建动态规划的逻辑。同时...

    获取最长公共子串

    3. 记录:在遍历过程中,同时记录下最大值和对应的结束位置,以便于找出最长公共子串。 4. 回溯:根据记录的最大值和结束位置,从dp数组回溯,构造出最长公共子串。 在编程实现时,可以使用Python这样的高级语言,...

    python实现求两个字符串的最长公共子串方法

    在Python编程语言中,求解两个字符串的最长公共子串是一项常见的字符串处理任务。这个问题的解决方案通常基于动态规划思想,即将问题分解为更小的子问题,并存储子问题的解以便于后续使用,从而避免重复计算。下面...

Global site tag (gtag.js) - Google Analytics