最長公共子序列和最長公共子串區別
最長公共子串（Longest Common Substring）與最長公共子序列（Longest Common Subsequence）的區別：
子串要求在原字串中是連續的，而子序列則只需保持相對順序一致，并不要求連續，
例如 X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}
那么，{a, 1, 1}是X和Y的最長公共子序列，但不是它們的最長公共字串，
最優子結構
思路
我們的目的是尋找兩個順序相對一致的序列
所以我們需要構建一個二維陣列進行統計，記錄遍歷的時候他們相同的地方
設有這樣的兩個序列:
{A,L,C,H,E,M,I,S,T}
{A,L,G,O,R,I,T,H,M,S}
第一行的意思可以看作空和空.空和A，，，的最長子序列都為0
從第二行開始，如果相同就將左上角的值復制加一填入，所以這里就填上 1（0+1）
到第三個，元素不同的話就將這個位置的左和上元素比較，填入最大的，這里上是0左是1，所以填入1；
以此類推
到了第二行，第二行與第二列元素一樣，就讀取左上角元素的復制后加一填入，1加1填入2
之后都是以此類推，最后得到了
狀態轉移方程代碼
通過以上的分解后，我們可以得到這樣一個狀態轉移方程
if(a===b){ //如果他們相同 table[row][col] = table[row - 1][co1 - 1] + 1; //我們找到他斜上角的那個值進行加一之后賦值 } else { table[row][col] = Math. max(table[row][col - 1]， table[row - 1][col]);//如果不相同，我們就填入元素上方和左邊最大的元素 }
回傳存盤的序列資訊
得到變化資訊的陣列后得出序列就很容易了
設定一個函式為lcs，對得到的變化資訊進行處理
設儲存每一次的資訊，如果xi=yj則為1，另外兩種情況為dis[][]中儲存為2,3；如1代表兩個都是，2代表行是左，3代表列是上
如果讀取到為1的值說明在這里進行了作左上角的變化，說明他是一樣的
使用遞回即可完成
void LCS(int i, int j,char *A,int dis[100][100]){ if (i == 0 || j == 0) return; if (dis[i][j] == 1){ LCS(i - 1, j - 1,A,dis); printf("%c ", A[i-1]); } else if (dis[i][j] == 3){ LCS(i - 1, j,A,dis); }else{ LCS(i, j - 1,A,dis); } }
最終代碼實作
合并整理后的代碼
#include<stdio.h> #include<string.h> char A[100] = "ABCBDAB"; char B[100] = "BDCABA"; int len[100][100];//最大子序列的生成矩陣 int dis[100][100]; //創建陣列dis[][]來儲存每一次的資訊，如果xi=yj則為1，另外兩種情況為dis[][]中儲存為2,3；如1代表兩個都是，2代表行是左，3代表列是上 void LCSLength(int n ,int m, char *x,char *y,int len[100][100],int dis[100][100]){ int i, j, k; for (i = 0; i <= n; i++) len[i][0] = 0;//讓列為0 for (i = 0; i <= m; i++) len[0][i] = 0;//讓第一行為0 for (i = 1; i <= n; i++){ for (j = 1; j <= m; j++){ if (x[i-1] == y[j-1]){ //若他們相等，則讓他等于左上角的元素加1 len[i][j] = len[i - 1][j - 1] + 1; dis[i][j] = 1; //記錄下來在這里是相等的，標記為1 }else if (len[i - 1][j] >= len[i][j - 1]){ //他們不相等的時候，取上和左元素最大的那個 len[i][j] = len[i - 1][j]; dis[i][j] = 3;//取上標記為3 }else{ len[i][j] = len[i][j - 1]; dis[i][j] = 2; //取左標記為2 } } } } void LCS(int i, int j,char *A,int dis[100][100]){ if (i == 0 || j == 0)//遞回到第0行就回傳 return; if (dis[i][j] == 1){ //如果變化值為1就找再前一個變化值 LCS(i - 1, j - 1,A,dis); printf("%c ", A[i-1]);//大于這個值，這里注意了，遞回后，他是從最底層的遞回開始列印，就是我們需要的順序了 } else if (dis[i][j] == 3){ LCS(i - 1, j,A,dis);//變化值為3，說明了應該找上邊的 }else{ LCS(i, j - 1,A,dis);//變化值為3，說明了應該找左邊的 } } int main() { int n = strlen(A); int m = strlen(B); printf("%d %d\n", n, m);//輸出兩個序列的長度 LCSLength(n,m,A,B,len,dis); printf("最大子序列長度：%d ", len[n][m]); //最后的一個按直接的結果，他的值就是最長的序列數 int i,j; for (i = 0; i <= n; i++){ for (j = 0; j <= m; j++){ printf("%d ", dis[i][j]); } puts(""); } puts("子序列為："); LCS(n,m,A,dis); }
得到的結果是
ENDING...
我家識寶又不知道跑哪去玩了？！有看見她請麻煩聯系我：https://www.cnblogs.com/kuailest/p/16871777.html,雖然她會飯點前回來~(*°▽°*)~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/530557.html
標籤：其他
上一篇：開源遇上華為云——DataX for HuaweiCloud OBS
下一篇：Helm干貨！速度圍觀！