#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; }
相关推荐
求最大公共子串 s1和s2最长公共子串 c/c++源代码
主要介绍了JavaScript实现求最大公共子串的方法,涉及javascript针对字符串的遍历、匹配、运算等相关操作技巧,需要的朋友可以参考下
两个字符串里求最长的公共子串
求最长的公共子串 求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长...
最大公共子串计算论文相似度:事件复杂度O(m*n),空间复杂度Omin(m,n)),可以用来计算两个字符串的最大公共子串长度、相似度;可以用于论文相似度量、地理信息等基于相似度量的查询等环境。由于空间复杂度低,因此可...
最大公共子串问题是IT行业的经典面试题之一,在生物信息等领域也有重要应用。该资源使用动态规划实现了最大公共子串查找算法,问题具体描述在Problem里,代码为code.py,调试结果请参考Readme。
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
求N个字符的最大公共子串的长度 从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下的字符按原来顺序组成的串是该串的子串。例如: “”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是...
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
公共子串计算,输入两个字符串,忽略大小写,输出公共子串的最大长度
主要介绍了java实现求两个字符串最大公共子串的方法,详细的描述了两个字符串的最大公共子串算法的实现,需要的朋友可以参考下
C++实现找出两个字符串中最大的公共子串
设计最大公共子串 第一步:输入字符s和t 第二步:将s和t拆分,建立一个二维数组 第三步:比如第一行第一列表示字符串s和t的第一个字符是否相等,相等返回1,不等返回0 第四步:分别求二维数组中斜线上的公共子串...
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
此代码描写了如何求得一个最大公共子串,用的语言为c语言
主要介绍了PHP实现求两个字符串最长公共子串的方法,涉及php字符串与数组的遍历、运算、判断等相关操作技巧,需要的朋友可以参考下
今天小编就为大家分享一篇python实现求两个字符串的最长公共子串方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
字符串相关的动态规划最大公共子序列最大公共子串编辑距离 简述这三个算法解决的问题和展示状态转移方程并且给出可通过执行的Python代码。 最大公共子序列 子序列是,一个字符串中的任意字符组成的序列,重点在于,...