求2個字符串的最長公共子序列和最長公共子字符串
一. 最長公共子序列
定義:
一個數(shù)列S疚顷，如果分別是兩個或多個已知數(shù)列的子序列曾沈，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
例如：輸入兩個字符串BDCABA和 ABCBDAB基协，字符串 BCBA和BDAB 都是是它們的最長公共子序列嗅蔬，則輸出它們的長度4剑按，并打印任意一個子序列. （Note: 不要求連續(xù)）
判斷字符串相似度的方法之一 - 最長公共子序列越長，越相似澜术。
思路:
窮舉方法:
窮舉法是解決最長公共子序列問題最容易想到的方法艺蝴，即對S的每一個子序列，檢查是否為T的子序列鸟废，從而確定它是否為S和T的公共子序列猜敢，并且選出最長的公共子序列。
S和T的所有子序列都檢查過后即可求出S和T的最長公共子序列盒延。S的一個子序列相應(yīng)于下標(biāo)序列1,2缩擂，...，n的一個子序列添寺。因此胯盯，S共有2^n個子序列。當(dāng)然，T也有2^m個子序列。
因此，蠻力法的時間復(fù)雜度為O(2^n * 2^m)脑又，這是指數(shù)級別叉趣。
動態(tài)規(guī)劃方法:
最優(yōu)子結(jié)構(gòu)性質(zhì)：
設(shè)序列 X=<x1, x2, …, xm> 和 Y=<y1, y2, …, yn> 的一個最長公共子序列 Z=<z1, z2, …, zk>泞边，則：
-
若
xm = yn，則zk = xm = yn則Zk-1是Xm-1和Yn-1的最長公共子序列君账；image 若
xm ≠ yn繁堡， 要么Z是Xm-1和Y的最長公共子序列，要么Z是X和Yn-1的最長公共子序列乡数。
若
xm ≠ yn且zk≠xm椭蹄，則Z是Xm-1和Y的最長公共子序列；若
xm ≠ yn 且 zk ≠yn净赴，則Z是X和Yn-1的最長公共子序列绳矩。
綜合一下：就是求二者的大者
遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。例如玖翅，在計(jì)算 X 和Y 的最長公共子序列時翼馆，可能要計(jì)算出 X 和 Yn-1 及 Xm-1 和 Y 的最長公共子序列。而這兩個子問題都包含一個公共子問題金度，即計(jì)算 Xm-1 和 Yn-1 的最長公共子序列应媚。
計(jì)算最優(yōu)值：
子問題空間中，總共只有O(m*n)個不同的子問題猜极，因此中姜，用動態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。
長度表C 和 方向變量B：
實(shí)現(xiàn)代碼:
/**
找出 兩個 字符串 的公共 子序列(動態(tài)規(guī)劃)
@param str1 字符串1
@param str2 字符串2
*/
void maxPublicSubSequence(char *str1, char *str2) {
assert(str1 != NULL && str2 != NULL);
// 字符串 1 長度
int str1Length = strlen(str1);
// 字符串 2 長度
int str2Length = strlen(str2);
// 開辟 二維 存儲 數(shù)組 (并初始化 值為:0)
int **postionArray = (int **)malloc(sizeof(int *) * (str1Length + 1));
for (int i = 0; i <= str1Length; i ++) {
postionArray[i] = (int *)malloc(sizeof(int) * (str2Length + 1));
}
for (int i = 0; i <= str1Length; i++) {
for (int j = 0; j <= str2Length; j++) {
postionArray[i][j] = 0;
}
}
// 循環(huán) 遍歷
for(int i = 1; i <= str1Length; i++) {
for(int j = 1; j <= str2Length; j ++) {
// 如果 兩個字符 相同
if (str1[i - 1] == str2[j - 1]) {
postionArray[i][j] = postionArray[i - 1][j - 1] + 1;
}
// 如果 兩個 字符 不同
else {
postionArray[i][j] = (postionArray[i - 1][j] > postionArray[i][j - 1]) ? postionArray[i - 1][j] : postionArray[i][j - 1];
}
}
}
for (int i = 0; i < str1Length; i++) {
for (int j = 0; j < str2Length; j++) {
printf("%d ", postionArray[i][j]);
}
printf("\n");
}
int i, j ;
for (i = str1Length, j = str2Length; i >= 1 && j >= 1;) {
if (str1[i - 1] == str2[j - 1]) {
printf("%c ", str1[i - 1]);
i --;
j --;
}
else {
if (postionArray[i][j - 1] > postionArray[i - 1][j]) {
j--;
}
else {
i --;
}
}
}
// 釋放開辟數(shù)組
for (int i = 0; i < str1Length; i++) {
free(postionArray[i]);
}
free(postionArray);
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
maxPublicSubSequenceTwo("ABCBDAB" , "BDCABA");
}
return 0;
}
二: 最長公共子串
題目:
給定兩個字符串跟伏，求出它們之間
最長的相同子字符串的長度丢胚。
思路:
窮舉法：
給定兩個字符串A和B，我們可以通過從A的第一個字符開始與B對應(yīng)的每一個字符進(jìn)行對比的方式找到最長的公共字串受扳。如果此時沒有找到匹的字母携龟，則移動到A的第二個字符處，然后從B的第一個字符處進(jìn)行對比勘高，以此類推峡蟋。
實(shí)現(xiàn)代碼:
#import <Foundation/Foundation.h>
/**
找出 兩個 字符串 的 最長 公共 子串 (窮舉法)
@param str1 字符串1
@param str2 字符串2
*/
void maxPublicSubStringOne(char *str1, char *str2) {
assert(str1 != NULL && str2 != NULL);
// 起始 位置
int startPosition = 0;
// 公共 子串 長度
int maxStringLength = 0;
// 循環(huán) 遍歷 所有 子字符串
for (int i = 0; i < strlen(str1); i ++) {
for (int j = 0; j < strlen(str2); j++) {
// 如果 兩個 字符 相等
if(str1[i] == str2[j]) {
// 繼續(xù) 比較 后面的字符
int k = 1;
while (str1[i + k] == str2[j + k] && str1[i + k] != '\0' && str2[j + k] != '\0') {
k ++;
}
// 如果 k 大于 最長 字符串
if (k > maxStringLength) {
// 公共 子串 長度
maxStringLength = k;
// 起始位置
startPosition = i;
}
}
}
}
if(maxStringLength > 0) {
for (int i = startPosition; i <= maxStringLength; i++) {
printf("%c ", str1[i]);
}
}
}
動態(tài)規(guī)劃-空間換時間
采用一個二維矩陣來記錄中間結(jié)果，矩陣的橫坐標(biāo)為字符串1的各個字符华望，矩陣的縱坐標(biāo)為字符串2的各個字符层亿。
舉例說明：假設(shè)兩個字符串分別為"bab"和"caba" (當(dāng)然我們現(xiàn)在一眼就可以看出來最長公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
可以看出，矩陣的斜對角線最長的那個就對應(yīng)著兩個字符串的最長公共子串立美。
不過在二維矩陣上找最長的由1組成的斜對角線也是件麻煩費(fèi)時的事，可以用下面的方法改進(jìn)：當(dāng)要在矩陣是填1時讓它等于其左上角元素加1方灾。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
這樣矩陣中的最大元素就是最長公共子串的長度建蹄。另外碌更，在構(gòu)造這個二維矩陣的過程中由于得出矩陣的某一行后其上一行就沒用了，所以實(shí)際上在程序中可以用一維數(shù)組來代替這個矩陣洞慎。
實(shí)現(xiàn)代碼：
/**
找出 兩個 字符串 的公共 子串(動態(tài)規(guī)劃)
@param str1 字符串1
@param str2 字符串2
*/
void maxPublicSubStringTwo(char *str1, char *str2) {
assert(str1 != NULL && str2 != NULL);
// 起始 位置
int startPosition = 0;
// 公共 子串 長度
int maxStringLength = 0;
// 字符串 1 長度
int str1Length = strlen(str1);
// 字符串 2 長度
int str2Length = strlen(str2);
// 開辟 二維 存儲 數(shù)組 (并初始化 值為:0)
int **postionArray = (int **)malloc(sizeof(int *) * str1Length);
for (int i = 0; i < str1Length; i ++) {
postionArray[i] = (int *)malloc(sizeof(int) * str2Length);
}
for (int i = 0; i < str1Length; i++) {
for (int j = 0; j < str2Length; j++) {
postionArray[i][j] = 0;
}
}
// 循環(huán) 遍歷
for(int i = 0; i < str1Length; i++) {
for(int j = 0; j < str2Length; j ++) {
// 如果 兩個字符 相同
if (str1[i] == str2[j]) {
// 判斷 釋放 是 邊界 情況
if (i == 0 || j == 0) {
// 邊界 情況
postionArray[i][j] = 1;
}
// 非邊界 情況
else {
postionArray[i][j] = postionArray[i - 1][j - 1] + 1;
}
if (postionArray[i][j] > maxStringLength) {
maxStringLength = postionArray[i][j];
startPosition = i - postionArray[i][j] + 1;
}
}
}
}
// 打印 字符串
if(maxStringLength > 0) {
for (int i = 0; i <= maxStringLength; i++) {
printf("%c ", str1[startPosition + i]);
}
}
// 釋放開辟數(shù)組
for (int i = 0; i < str1Length; i++) {
free(postionArray[i]);
}
free(postionArray);
}
9人點(diǎn)贊
