① 兩個字元串的所有公共最長子序列
/* 目標：輸出兩個字元串的所有公共最長子序列
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語言求解最長公共子字元串問題及相關的演算法
假定字元串採用堆分配方式，編寫一個程序，求兩個字元串S和T的一個最長公共子串
本題的思路：
本題要實現的演算法掃描兩個字元串。其中index指出最長公共子串在s中的序號，length指出最長公共子串的長度
堆分配存儲表示如下：
typedef struct{
char *ch;
int length;
}Hstring;
Status MaxComString(Hstring S,Hstring T,int &length){
index=0;
length=0;
i=0;
//令i作為掃描字元串S的指針
while(i<S.length){
j=0;
//令j作為掃描字元串T的指針
while(j<T.length){
if(s.ch[i]==T.ch[j]){
//找一個子串，其在字元串S中的序號為i，長度為length1
length1=i;
for(k=1;S.ch[i+k]==T.ch[j+k];k++)length1++;
if(length1>length){
//將較大長度值賦給index與length
index=i;
length=length1;
}
j=j+length1;//繼續掃描字元串T中第j=length1個字元之後的字元
}else{
j++;
}
}//while
i++;
}//while
printf("最長公共子串:");
for(i=0;i<length;i++)printf("%c",S.ch[index+i]);
return OK;
}
③ 尋找最長公共子串(高分)
小可來個最簡練的。程序已加上注釋並在vs2005和dev-c++下嚴格驗證通過。
程序已做修改，對多個字元串求最長公共子串。思路和求兩個字元串公共子串相似。原因是：多個字元串的公共子串首先必須是任何兩個字元串的公共子串。所以只需要先求出兩個字元串的最長公共子串然後用此子串再和其他字元串再求最長公共子串，最後的最長公共子串即是結果。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 1024;
const int M = 256;
void MaxSubString(char* str1,char* str2,char* s)
{
int i, j, k, index, max=0;/* 公共子串長度初始化為0 */
for(i=0; str1[i]; i++)
for(j=0; str2[j]; j++)
{
for(k=0; str1[i+k]==str2[j+k] && (str2[j+k] || str1[i+k]); k++)
; /* 此循環求公共子串的長度，長度為k */
if(k>max) /* 如果出現大於當前子串長度的子串，則替換子串位置和長度 */
{
index = j;
max = k;
}
}
for(i=0; i<max; i++)
s[i] = str2[index++];/* 求出最長公共子串 */
s[i]='\0';
}
int main(void)
{
int i,n;
char str[M][N],str1[N],s[N]; /* s[N]保存最長公共子串 */
while(1)
{
puts("Please input the number of strings:");
if(scanf("%d",&n)==1) /*剔除輸入格式錯誤並輸入字元串個數n*/
break;
fflush(stdin); /*清鍵盤緩沖區*/
}
fflush(stdin); /*由於下面fgets()函數和gets()函數一樣是從鍵盤緩沖區取得字元，故這里先清空鍵盤緩沖區，否則會少一次輸入*/
printf("Please input %d strings:\n",n); /* 輸入n個字元串 */
for(i=0;i<n;i++)
fgets(str[i],N,stdin); /*用安全可靠的函數fgets()取代不安全的gets()函數*/
strcpy(str1,str[0]); /* str1初值為str[0] */
for(i=1;i<n;i++)
{
MaxSubString(str1, str[i],s);/* 兩兩字元串找最長公共子串 */
strcpy(str1,s);/* s復制給str1再找 */
}
printf("MaxSubString: %s\n",s);/* 列印出最長公共子串 */
printf("length=%d\n",strlen(s)); /* 列印出最長公共子串長度 */
system("pause");
return 0;
}
④ C語言實現最長公共子串與最長公共子序列
給定兩個字元串s1="GeeksforGeeks"，s2="GeeksQuizGo"，則它們的最長公共子串為「Geeks」，長度為5。
運用動態規劃的思想，將兩個字元串映射為一張二維表，表格中的值代表到當前為止的最長公共子串的值，如下圖所示：
生成這張表的步驟（假設這張表為t[][], r為行標，c為列標）：
Code
整個演算法的時間復雜度為O(len1 * len2)，len1與len2分別為兩個字元串的長度。
最長公共子序列與最長公共子串的區別是，最長公共子序列不要求「連續匹配」，它的目的是找到兩個字元串中最大的公共部分。依然以s1="GeeksforGeeks"，s2="GeeksQuizGo"為例，它們的最長公共子序列為「Geekso」和「GeeksG」，長度為6。
它的二維表如下所示：
它的生成步驟與最長公共子序列的最大不同在第3步，最長公共子序列在遇到s1[r] != s2[c]情況時，不會將t[r][c]重置為0，而是選擇Max(t[r-1][c], t[r][c-1])作為新值，即它一直保存著前面已比較序列的最長公共序列值。
⑤ 最長公共子串
找出 最長、連續的 子字元串
遍歷X、Y的所有子字元串，找出 最長公共後綴 ，則最長公共後綴的長度就是最長公共子串的長度。
LCSSuffix[i][j] = LCSSuffix[i - 1][j - 1] + 1 （若X[i - 1] == Y[j - 1]）
0 （若X[i - 1] != Y[j - 1]）
列印最長遞增子序列的版本
O(nlogn)演算法復雜度的版本
定義數組outputList[A.length]，outputList[i]表示所有長度為i+1的遞增子序列的最小尾元素。
容易證明：outputList[]是一個遞增數組。
⑥ 尋找字元串數組的最長公共子串
所謂最長公共子串問題是尋找兩個或多個已知字元串最長的子串。例如字元串 「ABCD」與「ABCDE」、「FABCDE」的最長公共子串是「ABCD」……
值得注意的是，有些人把最長公共子序列、最長公共前綴與最長公共子串搞混淆了，請特別注意⚠️。
《高效演算法：競賽、應試與提高必修128例》中介紹了最長公共子串的演算法，不過只是找兩個字元串之間的最長公共子串， 並沒有給出任意個數 （此處當然指的是3個或以上）字元串的最長公共子串的求法。
現在用Python試寫如下：
最長子串還可以用lamada寫法，看起來更加簡潔
這個方法的復雜度是 O(n1 x n1 x (n1 + ... + nK)) ， 如果字元串不復雜，還是可以一用的😄。
⑦ 最長公共子串
又是樓主?好像這個問題已經回答過了
下面的程序是符合樓主要求的程序
//作者:hacker
//時間:9.12.2006
#include <stdio.h>
#include <string.h>
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用來判斷是否匹配的變數
for (i=1;i<=n;i++)//匹配長度的循環
for (j=0;j<n-i+1;j++)//y的起始位置的循環
for (k=0;k<m-i+1;k++)//x的起始位置的循環
{
count = 0;
for (l=0;l<i;l++)//判斷是否匹配,代碼可以優化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//記錄最大長度
start = j;//記錄最大長度的起起位置
}
}
if (maxlength==0)
printf("No Answer");
else
for (i=0;i<maxlength;i++)
printf("%c",y[start+i]);
}
下面的程序是真正的最長公共子串的程序
//作者:hacker
//時間:9.12.2006
#include <stdio.h>
#include <string.h>
int b[50][50];
int c[50][50];
void lcs(x,m,y,n)
char *x;
int m;
char *y;
int n;
{
int i;
int j;
for (i=1;i<=m;i++) c[i][0] = 0;
for (i=1;i<=n;i++) c[0][i] = 0;
c[0][0] = 0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
void show(i,j,x)
int i;
int j;
char* x;
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
show(i-1,j-1,x);
printf("%c",x[i-1]);
}
else
if (b[i][j]==2)
show(i-1,j,x);
else
show(i,j-1,x);
}
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
lcs(x,m,y,n);
show(m,n,x);
}
⑧ 最長公共子串和最長公共子序列的區別。舉個例子不要寫代碼。
應該是這樣：
字元串1：abcde
字元串2：abcdfe
那麼：
最長公共子串：abcd
最長公共子序列：abcde
就是公共子串，必須在待匹配字元串中連續，而公共子序列只需要相對順序匹配就行。
前者一般用KMP演算法，後者一般用動態規劃解決吧。
⑨ java求最大公共子串
二樓改的
c = b.substring(i,j-1);
之後下標越界沒了。
程序無法出結果，中間有死循環。當while語句執行完之後j是a.length();然後是執行內循環for語句for(j=b.length()-1;j>0;j--) 此時只比較J>0;。。。。好像是個死循環。最內層的循環可以在加一個int k來控制。多次運行導致cpu上升至100%的。
提供一種矩陣演算法，這是LCS的一種演算法：
public class stringCompare {
/**求最長匹配子字元串演算法
str數組記錄每行生成的最大值strmax
max數組記錄str數組最大時所處的列號nummaxj
最大子字元串為substring(nummax-strmax+1,strmax+1)
*/
public static void main(String[] args) {
String s1="asdfgxxcvasdfgc";
String s2="asdfxxcv";
int m=s1.length();
int n=s2.length();
int k=0;
int nummax=0;
int []str=new int[m];
int []max=new int[m];
int []num=new int[m];
for(int i=0;i<m;i++) //生成矩陣數組
for(int j=n-1;j>=0;j--)
{
if(s1.charAt(i)==s2.charAt(j))
if(i==0||j==0)
{
num[j]=1;
max[i]=j;
str[i]=1;
}
else
{
num[j]=num[j-1]+1;
if(max[i]<num[j])
{
max[i]=j;
str[i]=num[j];
}
}
else
num[j]=0;
}
for(k=0;k<m;k++) //求str數組的最大值
{
if(nummax<str[k])
{
nummax=str[k];
}
}
for(k=0;k<m;k++)
if(nummax==str[k])
System.out.println(s2.substring(max[k]-str[k]+1,max[k]+1));
}
}