兩個字元串的最長公共子串

『壹』 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＋＋編程求兩個字元串的最長公共子串

很復雜的