『壹』 如何使用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;
}
『貳』 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])作為新值，即它一直保存著前面已比較序列的最長公共序列值。
『叄』 求最長公共子序列的C語言程序
得到字元串m1,m2後，有一個為空則子列為空。
如果都不為空，開始下面的步驟。
求得兩列的長度分別為n1,n2。
動態生n2行n1列矩陣（二維數組）。
取m2中每個元素（記位置為i）與m1中元素（記位置為j）逐個比較，如果相等則為矩陣中相應行列坐標的元素賦值為1，否則為0（可用循環嵌套完成）。
比如m1(abc0cbad)m2(cba1abc)兩串的話，可以得到如圖所示矩陣。
然後，不難看出，要進行如下步驟。
定義max,用來記錄最大子列中元素個數。
定義數組l[n2],用來記錄最大子列的首字元地址（因為可能有不同最大子列，故用數組，而不是單個變數）。
判斷矩陣中每一個元素，是否為1，如果是則記下此時行地址到l數組，然後判斷相對於這個元素的下一行下一列的元素是否為1，如果是則繼續判斷，一直到為0。記下此次判斷（即一個while循環）中「1」的個數n，存入變數max。
對於矩陣中的每一個元素都這么判斷，如果判斷中n的值大於max那麼把n付給max，同時把這個子列的首地址付給l[0]，l[0]後面的元素全賦值為-1。如果，某次判斷得到的n與max相同，即有相同最大子列，那麼把它的首地址存入l數組的下一個位置。
當這個矩陣的每一個元素都判斷完畢後，會得到max,和數組l，然後用循環做如下輸出過程：依次以l數組中的每個元素為首地址，輸出m2字元串中以相應序號開頭的max個字元，那麼完成所有最大子列的輸出。
昨天失眠了，一直到今天凌晨3點多，腦袋渾渾噩噩的，本想幫你敲代碼，可是腦力不支了，估計敲出來也亂，還有問題的話，再討論452032545
『肆』 C語言求最長子序列
下面是你的代碼修改過後的結果，改過的地方都有注釋，另有測試樣例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最長子序列：9
4
-2 -3 8 -7
最長子序列：8
3
-2 -2 7
最長子序列：7
2
-1 5
最長子序列：5
1
-2
最長子序列：0
Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.
*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在這里再加一個判斷條件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是負數的話，結果應該是0，即一個都不選
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最長子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}
『伍』 最長 公共子序列問題（演算法分析 C++）
#include <iostream>
#include <string>
using namespace std;
//主函數
int main()
{
int m,n;
char *x,*y;
int **b,**c;
void LCSLength(int m,int n,char *y,char *x,int **c,int **b);
void LCS(int i,int j,char *x,int**b);
cout<<"請輸入兩個序列的長度："<<endl;
cin>>m>>n;
x=new char[m];
y=new char[n];
cout<<"請輸入兩個序列："<<endl;
cin>>x>>y;
b=new int *[m + 1]; // 注意這里，原式沒有+1
for (int i=0;i<=m;i++)
b[i]=new int[n + 1]; // 注意這里，原式沒有+1
c=new int *[m + 1];
for (int j=0;j<=m;j++)
c[j]=new int[n + 1]; // 注意這里，原式沒有+1
LCSLength(m,n,x,y,c,b);
cout<<"最長公共子序列的元素個數為"<<c[m][n]<<endl;
cout<<"該序列為:";
LCS(m,n,x,b); //注意後面的內容是清理，暫時先跳過去，你先搞定主程序先
/* delete []x;
delete []y;
for(int k=0;k<=m;k++)
delete []b[k];
delete []b;
for(int h=0;h<=m;h++)
delete []c[h];
delete []c;
*/
return 0;
}
//計算最優值
void LCSLength(int m,int n,char *y,char *x,int **c,int **b)
{
int i,j;
for(i=1;i<=m;i++)c[i][0]=0;
for(j=0;j<=n;j++)c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==y[j]){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 LCS(int i,int j,char *x,int**b)
{
if(i==0||j==0)return;
if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}
else if(b[i][j]==2)LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
『陸』 求一個最長公共子序列的 C++代碼
#include <iostream.h>
#include <iomanip.h>
#define MAX 99
//typedef char MM;
void main()
{ int i,j,m,n,h=0;
char x[MAX]={ ' ', ' '},y[MAX]={ ' ', ' '},b[MAX][MAX]={ ' '};
int c[MAX][MAX]={0};
char temp[MAX]={ ' '};
cout < < "**本程序可以求得字元數在99以內的任意兩個字元串的最大公共子序列**\n ";
cout < < "請輸入第一個字元串的長度m= ";
cin> > m;
cout < < "請輸入第一個字元串(「回車」結束)\n如果輸入的字元數超過m,則會出錯!\nx[ " < <m < < "]= ";
for(i=1;i <=m;i++)
cin> > x[i]; //鍵盤輸入x和y
cout < < "請輸入第二個字元串的長度n= ";
cin> > n;
cout < < "請輸入第二個字元串\ny[ " < <n < < "]= ";
for(i=1;i <=n;i++)
cin> > y[i];
for(i=1;i <=m;i++)c[i][0]=0; //動態規劃開始
for(i=1;i <=n;i++)c[0][i]=0;
for(i=1;i <=m;i++)
for(j=1;j <=n;j++)
{if(x[i]==y[j])
{c[i][j]=c[i-1][j-1]+1;
b[i][j]= '\\ ';
}else
if(c[i-1][j]> =c[i][j-1])
{ c[i][j]=c[i-1][j];
b[i][j]= '│ ';
}else{c[i][j]=c[i][j-1];
b[i][j]= '- ';
}
} //動態規劃結束
cout < < "c[m][n]中的內容：\n ";
for(i=0;i <=m;i++)
{for(j=0;j <=n;j++)
cout < <c[i][j];
cout < <endl;
}
cout < < "b[m][n]中的內容：\n ";
for(i=1;i <=m;i++)
{for(j=1;j <=n;j++)
cout < <b[i][j];
cout < <endl;
}
i=m,j=n;
while(1)
{if(i==0││j==0) break;
if(b[i][j]== '\\ '){
temp[h++]=x[i]; //反序記錄最長公共子序列到temp中
i=i-1,j=j-1;
}
else
if(b[i][j]== '│ ')
i=i-1;
else
j=j-1;}
cout < < "\nx[ " < <m < < "]和y[ " < <n < < "]的最長公共子序列為： ";
for(i=h-1;i> =0;i--) //格式化輸出最長公共子序列
if(i==h-1)
if(h==1)
cout < < "LCS: < " < <temp[i] < < "> ";
else
cout < < "LCS: < " < <temp[i];
else
if(i==0)
cout < < ", " < <temp[i] < < "> ";
else
cout < < ", " < <temp[i];
cout < < "\n " < <endl;
}
『柒』 求一個最長公共自序列的程序，C語言的，拜託了
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
for(i=0;i<m;i++) c[i][0]=0;
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){
for(j=1;j<n;j++){
if(x[i]==y[j]){
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 printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列長度為%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}
『捌』 C語言 最長的連續的公共子序列
#include<stdio.h>
#define M 7
#define N 7
int c[M][N];
int b[M][N];
int lcsLength(char x[],char y[])
{
int m=M-1;
int n=N-1;
int i,j;
for(i=0;i<M;i++)
c[i][0]=0;
for(j=0;j<N;j++)
c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==x[j])
{
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;
}
}
return c[m][n];
}
void lcs(int i,int j,char x[],int b[M][N])
{
if(i==0||j==0)
return;
if(b[i][j]==1)
{
lcs(i-1,j-1,x,b);
printf("%-c,%d\t",x[i],i);
}
else if(b[i][j]==2)
lcs(i-1,j,x,b);
else
lcs(i,j-1,x,b);
}
void main()
{
char x[]={'0','A','B','C','B','D','A'};
char y[]={'0','B','H','C','A','B','A'};
int i,j;
printf("%d\n",lcsLength(x,y));
printf("\n");
lcs(M-1,N-1,x,b);
}
『玖』 （演算法 c++）動態規劃法求解最長公共子序列 本人菜鳥求高手改錯幫忙完成 謝謝了
不是我不想幫你，但如果真要改的話，整個程序差不多要重寫了……首先你要確定此程序是上網刷題/比賽？還是自學演算法知識？如果你有很好的數學功底還可以自學知識，但比賽的話自學是絕對不夠的，那需要充分的交流，還有，養成良好的編程風格是一個極其重要的方面，在網上應該可以找到某些大牛的代碼集，運氣好還有注釋版的，可以多多借鑒。下面是一段代碼，NetBeans/G++編譯通過，你可以嘗試改成類結構的。^_^
#include <iostream>
using namespace std;
#define MAXLENGTH 20
// 這是偷懶的部分……不要介意哈
int maxLength[MAXLENGTH + 2][MAXLENGTH + 2];
int preChar[MAXLENGTH + 2][MAXLENGTH + 2];
/*
* 參數說明
* s1：待處理字元串1
* s2：待處理字元串2
* l1：s1長度（不包括字元串結束符'/0'）
* l2：s2長度（不包括字元串結束符'/0'）
*
* 參數中加const的目的是為了保護外部數據，防止因失誤而在函數內部改變了本因無需改變的數值。
*/
int LCSLength(const char* s1, const int l1, const char* s2, const int l2) {
/* 盡量不要在for等語句中定義變數，每個函數一開始最好就把需要的變數全部定義好，同時盡量賦予有意義的函數名 */
/* 當然，有時偷點懶是可以的，但你要確保過了幾個月後一看到代碼就能很快知道這是啥意思 */
int i, j;
/* maxLength用於存放中間數據，意義：maxLength[i][j]表示：s1前i個字元與s2前j個字元的最長子序列長度
* preChar用於存放當前最長子序列是由那一個自序列得來的
* 因本演算法特殊性，需要各額外2位的存儲空間
*/
/**/
for (i = 0; i <= l1; i++) maxLength[i][0] = 0;
for (j = 0; j <= l2; j++) maxLength[0][j] = 0;
for (i = 0; i <= l1; i++)
for (j = 0; j <= l2; j++) {
/* 如果s1第i個字元與s2第j個字元相同，則更新maxLength[i+1][j+1]存儲的最大值，和preChar存放的前綴自序列位置
* 下同
*/
if (s1[i] == s2[j] && maxLength[i + 1][j + 1] < maxLength[i][j] + 1) {
maxLength[i + 1][j + 1] = maxLength[i][j] + 1;
preChar[i + 1][j + 1] = 1;
}
if (maxLength[i + 1][j] < maxLength[i][j]) {
maxLength[i + 1][j] = maxLength[i][j];
preChar[i + 1][j] = 2;
}
if (maxLength[i][j + 1] < maxLength[i][j]) {
maxLength[i][j + 1] = maxLength[i][j];
preChar[i][j + 1] = 3;
}
}
/* 返回最長子序列長度 */
return maxLength[l1][l2];
}
/**
* s1、s2與上同
* i：s1當前字元序號
* j：s2當前字元序號
*
* i、j初始值為各自字元串長度
*/
void LCSOutput(const char* s1, const int i, const char* s2, const int j) {
if (i >= 0 && j >= 0) {
// 由於是逆向輸出，所以先遞歸，後輸出
switch (preChar[i][j]) {
case 1:
LCSOutput(s1, i - 1, s2, j - 1);
break;
case 2:
LCSOutput(s1, i - 1, s2, j);
break;
case 3:
LCSOutput(s1, i, s2, j - 1);
break;
default:
break;
}
if (s1[i] == s2[j])
cout << s1[i];
}
}
int main() {
cout << "最長公共子序列長度：" << LCSLength("1234567890", 10, "1358967", 7) << endl;
cout << "最長公共子序列（不確保唯一）：";
LCSOutput("1234567890", 10, "1358967", 7);
cout << endl;
return 0;
}