先來說明下什么是最長(zhǎng)公共子序列，什么是是最長(zhǎng)公共子串，舉一個(gè)實(shí)際例子，myblogs與belong，最長(zhǎng)公共子序列為blog（myblogs, belong），最長(zhǎng)公共子串為lo（myblogs, belong）也就是說子串要求在原字符串中是連續(xù)的，而最長(zhǎng)公共子序列則并不要求連續(xù)。

最長(zhǎng)公共子序列問題

問題描述

給兩個(gè)字條串X="ABCBDAB",Y="BDCABA",求這兩個(gè)字符串的最長(zhǎng)公共子序列。

問題分析

這里只求這個(gè)公共子序列的長(zhǎng)度。 利用動(dòng)態(tài)規(guī)劃的思想分析。 定義一個(gè)前綴概念：

給定一個(gè)序列X = <x1,x2 ,..., xm>，對(duì)于i = 0,1,...,m，定義X的第i前綴為Xi = <x1,x2 ,..., xi>。例如，若 X = <A,B,C,B,D,A,B>，則 X4 = <A,B,C,B>，X0為空串。

則減小問題的規(guī)模，X、Y都去掉一個(gè)字符時(shí)，他們的最長(zhǎng)公共子串和X與Y的最長(zhǎng)公共子串有什么關(guān)系呢?

令X = <x0,x1,x2 ,...>和Y = <y0,y1,y2 ,...> 為兩個(gè)序列，Z =<z0,z1,z2 ,...為X和Y的任意LCS。c[i,j]表示Xi和Yj的LCS的長(zhǎng)度,則： - 如果Xi = Yj，則 c[i,j]=c[i-1,j-1]+1。 - 如果 Xi ≠ Yj，則 c[i,j]=max(c[i-1,j],c[i,j-1])

此時(shí)要求i>0,j>0,即X、Y的字符個(gè)數(shù)都至少為兩個(gè)，因?yàn)樯厦娴倪f推公式都用到了c[i-1,j-1]

考慮初始條件，如果X,Y有一個(gè)為空串，則就沒有公共子序列了。

如果X,Y有一個(gè)為只含一個(gè)字符的子符串，則公共子串要么是沒有，可以看成是長(zhǎng)度為0，要么是就是這個(gè)字符了其長(zhǎng)度為1.

按這個(gè)思路，先計(jì)算初始條件，然后利用遞推公式計(jì)算所有值，代碼實(shí)現(xiàn)如下。

代碼實(shí)現(xiàn)

int lcs(string word1, string word2) {int size1 = word1.size();int size2 = word2.size();int max_length=0;int dp[size1][size2];//初值比較，字符串的第一個(gè)字符if(word1[0] == word2[0]){dp[0][0] =1;max_length = 1;}else{dp[0][0] =0;}//字符串word2的一個(gè)字符，各word1的所有字符for(int i = 1,j=0; i<size1; i++){if(word1[i] == word2[j]){dp[i][j] = 1;max_length = 1;}else{dp[i][j] = dp[i-1][j];}}//字符串word1的一個(gè)字符，各word2的所有字符for(int j=1,i=0; j<size2; j++){if(word1[i] == word2[j]){dp[i][j] = 1;max_length = 1;}else{dp[i][j] = dp[i][j-1];}}//利用上面的初始化值來迭代for(int i =1; i<size1; i++){for(int j=1; j<size2;j++){dp[i][j] =0;if(word1[i] == word2[j]){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}if(dp[i][j] > max_length ){max_length = dp[i][j] ;}}}return max_length; }

最長(zhǎng)公共子串問題

這里以leetcode上的一個(gè)最長(zhǎng)公共子數(shù)組問題來說明。

問題描述

給數(shù)組A,B,求A,B的最長(zhǎng)公共子數(shù)組，如 Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 解釋，最長(zhǎng)公共子數(shù)組為 [3, 2, 1]。

問題分析

和最長(zhǎng)公共子序列問題類似，不過c[i][j]定義應(yīng)該是稍有不同的，這里的c[i][j],表示A[0...i]和B[0...j]的最長(zhǎng)公共子串，且此公共子串中一定包含A[i],B[j]的，最長(zhǎng)公共子序列中的定義可以不包括A[i],B[j]的。

此時(shí)的遞推公式也稍有不同了：

• 如果A[i] = B[j]，則 c[i,j]=c[i-1,j-1]+1。
• 如果 A[i] ≠ B[j]，則 c[i,j]=0

代碼實(shí)現(xiàn)

int findLength(vector<int>& A, vector<int>& B) {int asize=A.size();int bsize=B.size();int dp[asize][bsize];int max = 0;for(int i=0,j=0; i<asize; i++){if(A[i] == B[j]){dp[i][j] = 1;max = 1;}else{dp[i][j] = 0;}}for(int i=0,j=0; j<bsize; j++){if(A[i] == B[j]){dp[i][j] = 1;max = 1;}else{dp[i][j] = 0;}}for(int i=1; i<asize; i++){for(int j = 1; j<bsize; j++){if(A[i] == B[j]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = 0;}if(dp[i][j] > max){max = dp[i][j];}}}return max; }

todo: - 補(bǔ)充c數(shù)組的表格 - 加求具體序列的方法

總結(jié)

以上是生活随笔為你收集整理的两个字符串的最长公共子序列长度_【面试】动态规划-之最长公共子序列、最长公共子串问题...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。