如"abcecade","dgecadde"的最大子串为"ecad"

2010-11-15 10:40:46

8 Answers

把字符串1(长度m)横排,串2(长度n)竖排,得到一个m×n的矩阵c,矩阵的每个元素的值如下,如果m[i]=n[j],则c[j][i]=1,否则,c[j][i]=0。然后找出矩阵中连续是1的对角线最长的一个,则对角线的长度就是公共子串的长度.
经过改进,可以不需要构造矩阵,因为第i行如果有字母匹配,其取值仅与第i-1行相关,若m[i]=n[j],则c[j][i] = c[j-1][i-1] + 1,这样仅需要记录一个长度为m的一维数组就可以了。

#include <stdio.h> #include <stdlib.h> char * StringSearch( char * str1, char * str2 ) { int i; int j; char* ptempBuffer1; char* ptempBuffer2; char* pwork; char* plast; char* ptemp; char* retstr; int resultIndex = 0; int resultLength = 0; int str1Size = 0; int str2Size = 0; ptempBuffer1 = str1; while( *ptempBuffer1 != '\0' ) { ptempBuffer1++; str1Size++; } ptempBuffer2 = str2; while( *ptempBuffer2 != '\0' ) { ptempBuffer2++; str2Size++; } ptempBuffer1 = ( char * ) malloc( str1Size ); pwork = ptempBuffer1; memset( pwork, 0, str1Size ); ptempBuffer2 = ( char * ) malloc( str1Size ); plast = ptempBuffer2; memset( plast, 0, str1Size ); for( i = 0; i < str2Size; i++ ) { for( j = 0; j < str1Size; j++ ) { if( *( str1 + j ) == *( str2 + i ) ) { if( j == 0 ) { *( pwork + j ) = 1; } else { *( pwork + j ) = *( plast + j - 1 ) + 1; } if( resultLength < *( pwork + j ) ) { resultIndex = j; resultLength = *( pwork + j ); } } else { *( pwork + j ) = 0; } } ptemp = pwork; pwork = plast; plast = ptemp; } retstr = ( char * ) malloc( resultLength + 1 ); memcpy( retstr, str1 + resultIndex - resultLength + 1, resultLength ); *( retstr + resultLength ) = '\0'; printf( "resultIndex = %d, resultLength = %d\n", resultIndex, resultLength ); free( ptempBuffer1 ); free( ptempBuffer2 ); return retstr; } int main(int argc, char *argv[]) { char* ret = NULL; ret = StringSearch( "adbccadebbca", "edabccadece" ); printf( "result String is %s\n", ret ); free( ret ); system("PAUSE"); return 0; }

为了方便,采用了两个容量为m的一维数组来保存运行中的结果,空间复杂度为m+n+2m(保存打印输出的结果字符串可以不需要),也就是O(m+n)。由于需要事先遍历字符串得到长度,算法复杂度为mn + m + n,O(m*n)级别。 

2010-11-15 12:43:52

JavaScript版(其他语言类似):

function getMaxIntersec(a, b) { var aLen = a.length; var bLen = b.length; var index = 0, beginIndex = 0, endIndex = 0; for(var index = 0;index < aLen;index++) { var i = 0, begin = index, end = index; var aChar = a.charAt(index); while(i < bLen && aChar != b.charAt(i)) { i++; } if(i == bLen) continue; while(end < aLen && i < bLen && a.charAt(end) == b.charAt(i)) { end++; i++; } if ((end - begin) > (endIndex - beginIndex)) { beginIndex = begin; endIndex = end; } } return a.substring(beginIndex, endIndex); } alert(getMaxIntersec("abcecade", "dgecadde"));//ecad
2010-11-15 14:17:09

如@马瑜所说,同样是按照矩阵的的方法,可以直接按对角线遍历所有矩阵元素,这样只要一个变量来记录m[i]与n[j]是否相等就行,当m[i]=n[j],则c = c + 1,否则c=0,这样时间复杂度是O(m*n),由于没有借用数组来存储中间值,空间复杂度会小很多。PHP写的代码如下:

function str_same($s1,$s2){ $len1 = strlen($s1); $len2 = strlen($s2); $max = $index = $m = 0; for($i=0;$i<$len1;$i++){ for($j=0,$k = $i;$j<$len2 && $k<$len1;$j++,$k++) {//遍历左下对角线 if($s2{$j} == $s1{$k}) { if( $j==0 ) $m = 1; else $m++; }else{ $m = 0; } if($m > $max) { $max = $m; $index = $j; } //echo $j,$k,$m,"\n"; } if( $i==0 ) continue;//如果$i是0,只要遍历中间的对角线 for($k=0,$j = $i;$j<$len2 && $k<$len1;$j++,$k++) {//遍历右上对角线 if($s2{$j} == $s1{$k}) { if( $k==0 ) $m = 1; else $m++; }else{ $m = 0; } if($m > $max) { $max = $m; $index = $j; } //echo $j,$k,$m,"\n"; } } return substr($s2,$index-$max+1,$max); } echo str_same('abcecade','dgecadde');//ecad
2010-11-15 15:38:04

DP(动态规划)解:
时间复杂度为O(nm),空间复杂度也为O(nm)

#include <stdio.h> #include <string.h> void print_table(char *str1,char *str2,int **pf) { int i,j,row,col; row = strlen(str1); col = strlen(str2); printf("\t\t"); for (i=0; i<col; i++) printf("%c\t",str2[i]); for (i=0; i<=row; i++) { for (j=0; j<=col; j++) { if (j == 0) { printf("\n"); if (i) printf("%c\t",str1[i-1]); else printf("\t"); } printf("%d\t",pf[i][j]); } } } int commstr(char *str1, char *str2) /* 返回str1,str2的最长公共之串长度*/ { int len1=strlen(str1),len2=strlen(str2),row,col,max=0; int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间 for (row=0; row<len1+1; row++) pf[row] = new int[len2+1]; //数组赋初值 for (row=0; row<len1+1; row++) pf[row][0] = 0; for (col=0; col<len2+1; col++) pf[0][col] = 0; for (row=1; row<=len1; row++) for (col=1;col<=len2; col++) { if (str1[row-1] == str2[col-1]) { pf[row][col] = pf[row-1][col-1] + 1; max = pf[row][col] > max ? pf[row][col] : max; } else pf[row][col] = 0; } print_table(str1,str2,pf); //空间回收 for (row=0; row<len1+1; row++) delete[] pf[row]; delete[] pf; return max; } int main(int argc,char **argv) { if (argc >= 3) { printf("String:\n\t1. %s\n\t2. %s\n",argv[1],argv[2]); printf("\nmax substr length:%d\n",commstr(argv[1],argv[2])); } return 0; }

2010-11-15 17:26:54
main(); function main() { var a = 'abcecade'; var b = 'dgecadde'; var c = test(a, b); console.log(c); c = test(b, a); console.log(c); } function test(a, b) { var sl = ss = a; if(a.length > b.length) { ss = b; } else { sl = b; } for(var sublen = ss.length; sublen > 0; sublen--) { for(var i = 0; i + sublen <= ss.length; i++) { if(sl.indexOf(ss.substr(i, sublen)) != -1) { return ss.substr(i, sublen); } } } }
2010-11-15 18:43:33

Longest Common Substring和Longest Common Subsequence是有区别的
X =
Y =
X和Y的Longest Common Sequence为,长度为4
X和Y的Longest Common Substring为 长度为2
其实Substring问题是Subsequence问题的特殊情况,也是要找两个递增的下标序列
使
xi1 == yj1
xi2 == yj2
......
xik == yjk
与Subsequence问题不同的是,Substring问题不光要求下标序列是递增的,还要求每次
递增的增量为1, 即两个下标序列为:

类比Subquence问题的动态规划解法,Substring也可以用动态规划解决,令
c[i][j]表示Xi和Yi的最大Substring的长度,比如
X =
Y =
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
动态转移方程为:
如果xi == yj, 则 c[i][j] = c[i-1][j-1]+1
如果xi ! = yj, 那么c[i][j] = 0
最后求Longest Common Substring的长度等于
max{ c[i][j], 1<=i<=n, 1<=j<=m}

/** 找出两个字符串的最长公共连续子串的长度 ** author :liuzhiwei ** data :2011-08-16 **/ #include "stdio.h" #include "string.h" #include "stdlib.h" int longest_common_substring(char *str1, char *str2) { int i,j,k,len1,len2,max,x,y; len1 = strlen(str1); len2 = strlen(str2); int **c = new int*[len1+1]; for(i = 0; i < len1+1; i++) c[i] = new int[len2+1]; for(i = 0; i < len1+1; i++) c[i][0]=0; //第0列都初始化为0 for(j = 0; j < len2+1; j++) c[0][j]=0; //第0行都初始化为0 max = -1; for(i = 1 ; i < len1+1 ; i++) { for(j = 1; j < len2+1; j++) { if(str1[i-1]==str2[j-1]) //只需要跟左上方的c[i-1][j-1]比较就可以了 c[i][j]=c[i-1][j-1]+1; else //不连续的时候还要跟左边的c[i][j-1]、上边的c[i-1][j]值比较,这里不需要 c[i][j]=0; if(c[i][j]>max) { max=c[i][j]; x=i; y=j; } } } //输出公共子串 char s[1000]; k=max; i=x-1,j=y-1; s[k--]='\0'; while(i>=0 && j>=0) { if(str1[i]==str2[j]) { s[k--]=str1[i]; i--; j--; } else //只要有一个不相等,就说明相等的公共字符断了,不连续了 break; } printf("最长公共子串为:"); puts(s); for(i = 0; i < len1+1; i++) //释放动态申请的二维数组 delete[] c[i]; delete[] c; return max; } int main(void) { char str1[1000],str2[1000]; printf("请输入第一个字符串:"); gets(str1); printf("请输入第二个字符串:"); gets(str2); int len = longest_common_substring(str1, str2); printf("最长公共连续子串的长度为:%d\n",len); system("pause"); return 0; }

参考http://blog.csdn.net/hackbuteer1/article/details/6686931

2010-11-15 20:07:02
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#中using指令的几种用法

    using + 命名空间名字,这样可以在程序中直接用命令空间中的类型,而不必指定类型的详细命名空间,类似于Java的import,这个功能也是最常用的,几乎每个cs的程序都会用到

  • C#实例解析适配器设计模式

    将一个类的接口变成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够一起工作

  • 使用托管C++粘合C#和C++代码(二)

    本文实现一下C++代码调用C#代码的过程。我构造一个简单并且直观的例子:通过C++ UI 触发C# UI.

  • C#开发高性能Log Help类设计开发

    项目中要在操作数据库的异常处理中加入写Log日志,对于商业上有要求,写log时对其它操作尽可能影响小,不能因为加入log导致耗时太多

  • Async和Await使异步编程更简单

    C#5.0中async和await两个关键字,这两个关键字简化了异步编程,之所以简化了,还是因为编译器给我们做了更多的工作

  • C#开发中的反射机制

    反射的定义:审查元数据并收集关于它的类型信息的能力。元数据(编译以后的最基本数据单元)就是一大堆的表,当编译程序集或者模块时,编译器会创建一个类定义表,一个字段定义表,和一个方法定义表等

  • C#运行时相互关系

    C#运行时相互关系,包括运行时类型、对象、线程栈和托管堆之间的相互关系,静态方法、实例方法和虚方法的区别等等

  • C#协变和逆变

    “协变”是指能够使用与原始指定的派生类型相比,派生程度更大的类型,“逆变”则是指能够使用派生程度更小的类型

  • C#基础概念之延迟加载

    延迟加载(lazy load)是Hibernate3关联关系对象默认的加载方式,延迟加载机制是为了避免一些无谓的性能开销而提出来的,所谓延迟加载就是当在真正需要数据的时候,才真正执行数据加载操作

  • C#中的索引器的简单理解和用法

    C#中的类成员可以是任意类型,包括数组和集合。当一个类包含了数组和集合成员时,索引器将大大简化对数组或集合成员的存取操作

  • 使用托管C++粘合C#和C++代码(一)

    C#在xml读写,数据库操纵,界面构造等很多方面性能卓越;C++的效率高,是底层开发的必备武器

  • 深入C# 序列化(Serialize)、反序列化(Deserialize)

    C#中的序列化和反序列化,序列化是.NET运行时环境用来支持用户定义类型的流化的机制