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

『壹』 C语言编程 查找两字符串的最长公共子串 如"I am a student."与"R u a student"最长公共子串是"student"

//有个问题是,空格应该也算字符吧，所以没考虑空格。就像你那个例子，最长公共字串应该是//“student”,包含空格.还有,就是我这个应该不是很好的方法，效率比较低，我是先让串//1不动，串2先从第1个字符开始与串1比较，然后串2从第2个字符开始于串1比较，都比较完了，///串1向右挪动一个位置
#include<stdio.h>
intmain()
{
	charstr1[100]={0},str2[100]={0};
	printf("pleaseinputtwostrings:
");
	gets(str1);//读入字串
	gets(str2);
	char*p1=str1;//分别用来存str1和str2的当下比较位置
	char*p2=str2;
	intmax=0,num=0;//max存放比较后最长字串长度，num是这一轮比较公共字串长度
	char*start;//存放最大串起始位置
while(*p1!='')//先是串1大循环
{
	p2=str2;//p2是串2首地址
while(*p2!='')
	{
	char*begin=p1;//begin是串1当前比较位置
	char*begin2=p2;//begin2是串2开始比较位置
	num=0;//比较前初始化为0
	while(*begin!=''&&*begin2!='')//一轮新的比较
		{
		if(*begin==*begin2)//若相同，num++；
		{num++;begin++;begin2++;}
		elsebreak;
	}
if(num>max)//若新比较出的字串更长，则替换max值和start内容
		{max=num;
		start=p1;}
	p2++;//串2右移1位
}
p1++;//串1右移1位
}
while(max--)//输出串
printf("%c",*start++);
printf("
");
}

『贰』 如何求两个字符串的最长子串

//求使用最长子串使用LCS算法
char* LCS(char left[],char right[]) { //获取左子串的长度,获取右子串的长度 int lenLeft=strlen(left),lenRight=strlen(right),k; //注意这里要写成char型,而不是int型,否则输入整型数据时会产生错误。 //矩阵c纪录两串的匹配情况 char*c=malloc(lenRight),*p; //int c[M][M]={0};//当将c申明为一个二维数组时 int start,end,len,i,j;//start表明最长公共子串的起始点，end表明最长公共子串的终止点 end=len=0;//len表示最长公共子串的长度 for(i=0; i<lenLeft; i++) //串1从前向后比较 { //串2从后向前比较,为什么要从后向前呢?是把一维数组c[ ]当二维数组来用, //如果要从前向后,可以将c申明为一个二维数组c[M][M].但程序要做相应调整. // for(j=0;j<lenRight;j++)//当c申明为一个二维数组时 for(j=lenRight-1; j>=0; j--) { if(left[i] == right[j])//元素相等时 { if(i==0||j==0) c[j]=1;//c[i][j]=1; else { c[j]=c[j-1]+1;//c[i][j]=c[i-1][j-1]+1; } } else c[j] = 0; //c[i][j]=0; if(c[j] > len) //if (c[i][j]>len) { len=c[j]; //len=c[i][j]; end=j; } } } start=end-len+1; //数组p纪录最长公共子串 p =(char*)malloc(len+1); for(i=start; i<=end; i++) { p[i-start] = right[i]; } p[len]='\0'; return p; } void main() { char str1[M],str2[M]; printf("请输入字符串1:"); gets(str1) printf("请输入字符串2:"); gets(str2); printf("最长子串为:"); printf("%s\n",LCS(str1,str2)); }

『叁』 两个字符串的所有公共最长子序列

/* 目标：输出两个字符串的所有公共最长子序列
date: 09-11-26
BY: zggxjxcgx
算法： 判断较短串是否为较长串的子序列，如果是则得到结果；
否则，对较短串进行逐个字符删除操作（将字符替换为'#'表示删除）。
删除操作用递归函数进行实现。每层递归删除一个字符，
若删除一个字符后未得到匹配子序列，则还原该字符所在位置。
第n层递归未找到匹配子序列，则将递归层数加1，重复删除直到剩下空串。

*/
#include<stdio.h>
#include<string.h>
int dep=0; /* 较短串的长度 */
int depflag=0; /*下一步要探测的深度 */
int lastflag=0; /* 是否找到匹配子序列，1为找到 */
int count=0; /* 目标结果的个数 */

int mystrcmp(char *s1,char *s2) /* 判断s2是否为 s1的子串 */
{ while(*s1 && *s2)
if(*s2=='#') s2++;
else if(*s2 == *s1) { s1++; s2++; }
else s1++;

while(*s2=='#') s2++;
if(*s2=='\0') return 1;
return 0;
}
void pristr(char *str) /* 打印最长子序列 */
{ if(0==count++) printf("\n公共最长子序列：\n");
printf("%2d:",count);
while(*str)
{ if(*str!='#')
printf("%c",*str);
str++;
}
printf("\n");
}

/*递归函数求最长子序列。start 控制下一个要检测的字符,deptemp控制递归的深度,first为's'表示第一层递归 */
int fun(char *str1,char *str2,char *start,int deptemp,char first)
{ int i=0,j=0;
char *s,cback;
do
{ s=start;
if('s'==first) deptemp=depflag; /* 在第一层设置递归深度 */
while(*s)
{ if(*s=='#') { s++; continue; }
cback=*s; *s='#'; /* 删除当前字符*/
if(mystrcmp(str1,str2)) { pristr(str2); lastflag=1; } /*找到匹配，将lastflag设为1，在完成深度为deptemp+1的探测（找到所有匹配）后退出递归 */
else if(deptemp>0) fun(str1,str2,s+1,deptemp-1,'n'); /* 深度探测，s+1表示从下一个位置开始删除 */
*s=cback; s++; /* 还原该位置的字符，以便下次进行探测 */
}
if('s'==first) ++depflag; /* 删除depflag+1个字符还未找到，则递归深度加1 */
}while(depflag<dep-1 && 's'==first && 0==lastflag); /* 第一层递归具有特殊意义，由三个变量标记是否第一层 */
if(lastflag) return 1; /* lastflag 为1 表示找到匹配子序列 */
return 0;
}
void main()
{ char *s1,*s2;
char st1[]="asfdebjewcwedwk";
char st2[]="sabscdkwss"; // kwfsa
if(strlen(st1)>strlen(st2)) s1=st1,s2=st2; /* 将s1设为较长的串 */
else s1=st2,s2=st1;

printf("\nstr1:%s\nstr2:%s\n",s1,s2);
dep=strlen(s2); /* 得到较短串的长度 */
if(mystrcmp(s1,s2)) pristr(s2);
else if(0==fun(s1,s2,s2,0,'s')) printf("\n没有公共元素！\n");
// printf("%d\n",mystrcmp("afdebjewcwedw","abcdw#"));
}

『肆』 用C语言求两个字符串的最长公共子串并输出

char s1[256] = "abc moshoushijie xyz";
char s2[256] = "def moshoushijie mpq";

要求输出 " moshoushijie "这个字符串吗?

『伍』 求两个字符串最大公共子串问题

已改，看注释

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct
{
char str[MaxSize] ;
int len ;
}SeqString ;

int SubSeqString( SeqString *Sub , SeqString S , int pos , int len )
{
int i ;
if( pos < 0 || pos > S.len || len > S.len - pos || len < 1 )
{
Sub -> len = 0 ;
return 0 ;
}
else
{
for( i = 0 ; i < len ; i ++ )
{
Sub -> str[i] = S.str[i+pos] ;
}
Sub->str[i] = '\0'; // 字符串结束
Sub -> len = len ;
return 1 ;
}
}

int MaxSameSeqString( SeqString S , SeqString T , SeqString *M )
{
int i , j , k , t , pos ;
int len = 0 , maxlen = 0 ;
for( i = 0 ; i < S.len ; i++ )
{
k = i ;

for( j = 0 ; j < T.len ; j++ )
{
t = j ;
len = 0; // len赋值0
if( S.str[i] == T.str[j] )
{
while( S.str[k++] == T.str[t++] )
len++ ;
if( maxlen < len )
{
maxlen = len ;
pos = i ;
}
}
}
}
if( maxlen >= 1 )
{
SubSeqString( M , S , pos , maxlen ) ; // 参数是maxlen，不是len
return 1 ;
}
return 0 ;
}

int main()
{
SeqString X , Y ;
SeqString *R = (SeqString*)malloc(sizeof (SeqString));
char a[MaxSize] , b[MaxSize] ;
scanf( "%s" , a ) ;
scanf( "%s" , b ) ;
int alen , blen ;
alen = strlen(a) ;
blen = strlen(b) ;
X.len = alen ;
Y.len = blen ;
strcpy( X.str , a ) ;
strcpy( Y.str , b ) ;
MaxSameSeqString( X , Y , R ) ;
printf("%s" , R -> str );

return 0 ;}

『陆』 求两个字符串的最长公共子串，要求输入两个字符串，输出他们的最长公共子串，包括长度。

难~
关注

『柒』 求两个输入的字符串的最长公共子串

1. 算法：求两个字符串的最长公共子串

2. 原理：

（1） 将连个字符串分别以行列组成一个矩阵。

（2）。若该矩阵的节点对应的字符相同，则该节点值为1。

（3）当前字符相同节点的值 = 左上角(d[i-1, j-1])的值 +1，这样当前节点的值就是最大公用子串的长。

(s2)bcde

(s1)

a0000

b1000

c0200

d0030

3. 结果：只需以行号和最大值为条件即可截取最大子串

C# code:

[csharp]view plainprint?

publicstaticstringMyLCS(strings1,strings2)

{

if(String.IsNullOrEmpty(s1)||String.IsNullOrEmpty(s2))

{

returnnull;

}

elseif(s1==s2)

{

returns1;

}

intlength=0;

intend=0;

int[,]a=newint[s1.Length,s2.Length];

for(inti=0;i<s1.Length;i++)

{

for(intj=0;j<s2.Length;j++)

{

intn=(i-1>=0&&j-1>=0)?a[i-1,j-1]:0;

a[i,j]=s1[i]==s2[j]?1+n:0;

if(a[i,j]>length)

{

length=a[i,j];

end=i;

}

}

}

returns1.Substring(end-length+1,length);

}

『捌』 PHP怎么做出两个字符串的最长公共子串

矩阵法
原理：字符串1：string1＝＇aabbccdd＇字符版串2：string2＝＇accbbcdd＇
用string1的每个字符与string2的每个字符相比较，相等写权做1．不等写作0，则 如下所示：
第一行：10000000
第二行：10000000
第三行：00011000
第四行：00011000
第五行：01100100
第六行：01100100
第七行：00000011
第八行：00000011
可以看到1的对角线连起来最长的那行就是所求字符串，即加删除线的部分，可得到字符串bbc和cdd

『玖』 编写一个js方法,求2个字符串的最长公共子串的长度

<!DOCTYPEHTML>
<html>
<head>
<metacharset="UTF-8"/>
<title>JavaScript随机显示文字</title>
<styletype="text/css">
table{
	margin:0auto;
	border:1pxsolidblack;
	border-collapse:collapse;
}

td{
	border:1pxsolidblack;
}
</style>
<scriptsrc="jquery-1.8.0.min.js"></script>
<scripttype="text/javascript">
	//abcde
//dssdbcdeffg
varfinder=function(str1,str2,start,len)
{
	if(null==start)
	{
		start=-1;
		vars=str1.length<=str2.length?str1:str2;
		varl=str1.length>str2.length?str1:str2;
		str1=s;
		str2=l;
	}
	
	start++;
	
	if(!len)
	{
		len=str1.length;
	}
	
	varend=start+len;
	if(end>str1.length)
	{
	if(len==1)
{
	return0;
}
		returnfinder(str1,str2,-1,--len);
	}
	vartemp=str1.substring(start,end);
	if(str2.indexOf(temp)!=-1)
	{
		returntemp.length;
	}
	returnfinder(str1,str2,start,len);
}
varlen=finder("dssdbcdeffffgadfaf","abcdesdfsdffffgd");
console.debug(len);
</script>
</head>
<bodystyle="text-align:center;">
	<tableid="relTable">
	</table>
</body>
</html>

『拾』 用C＋＋编程求两个字符串的最长公共子串

很复杂的