生活随笔
收集整理的這篇文章主要介紹了
动态规划算法---求最长公共子序列
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
最長(zhǎng)公共子序列和最長(zhǎng)公共子串區(qū)別
?????? 最長(zhǎng)公共子串（Longest Common Substring）與最長(zhǎng)公共子序列（Longest Common Subsequence）的區(qū)別： 子串要求在原字符串中是連續(xù)的，而子序列則只需保持相對(duì)順序一致，并不要求連續(xù)。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最長(zhǎng)公共子序列，但不是它們的最長(zhǎng)公共字串。
一、最長(zhǎng)公共子序列
具體的算法思想?yún)⒖家韵挛恼?#xff1a;
?
http://blog.csdn.net/lisonglisonglisong/article/details/41548557
http://blog.csdn.net/zhongkeli/article/details/8847694
只求最長(zhǎng)子序列長(zhǎng)度
如果僅僅需要知道最長(zhǎng)子序列的長(zhǎng)度值，代碼如下：
?
[cpp]?view plain?copy
#include?<vector>??#include?<string>??#include?<iostream>??#include?<string.h>??#include?<sstream>??using?namespace?std;????//最長(zhǎng)公共子串（LCS）??//二維數(shù)組veca記錄的是兩個(gè)字符串Xi和Yj的LCS長(zhǎng)度??int?LCS_length(const?string?&str1,?const?string?&str2,?vector<vector<int>?>?&veca)?{??????int?i,?j;??????int?biggest?=?0;??????if?(str1?==?""?||?str2?==?"")??????????return?0;????????for?(i?=?0;?i?<=?str1.length();?i++)?{??? //初始化veca[][]????????veca[i][0]?=?0;??????}??????for?(j?=?0;?j?<=?str2.length();?j++)?{? ////初始化veca[][]????????veca[0][j]?=?0;??????}??????for?(i?=?1;?i?<=?str1.length();?i++)?{??????????for?(j?=?1;?j?<=?str2.length();?j++)?{??????????????if?(str1[i?-?1]?==?str2[j?-?1])?{??????????????????veca[i][j]?=?veca[i?-?1][j?-?1]?+?1;??????????????}??????????????else?{??????????????????if?(veca[i?-?1][j]?>=?veca[i][j?-?1])??????????????????????veca[i][j]?=?veca[i?-?1][j];??????????????????else??????????????????????veca[i][j]?=?veca[i][j-1];??????????????}??????????}??????}??????return?veca[str1.length()][str2.length()];??}????int?main()?{??????string?input;??????getline(cin,?input);??????????stringstream?ss(input);??????????string?str1,?str2;??????ss?>>?str1;??????ss?>>?str2;??????//將veca初始化為一個(gè)二維數(shù)組,其行列值分別為str1和str2的長(zhǎng)度加1??????//二維數(shù)組veca記錄的是兩個(gè)字符串Xi和Yj的LCS長(zhǎng)度??????vector<vector<int>?>?veca(str1.length()?+?1,?vector<int>(str2.length()?+?1));??????cout?<<?LCS_length(str1,?str2,?veca)?<<?endl;??????return?0;??}??
結(jié)果：
?
動(dòng)態(tài)規(guī)劃解決LCS問題的時(shí)間復(fù)雜度為?O(mn)，這比簡(jiǎn)單的遞歸實(shí)現(xiàn)要快多了?？臻g復(fù)雜度是O(mn)，因?yàn)槭褂昧艘粋€(gè)動(dòng)態(tài)規(guī)劃表。
要輸出一個(gè)LCS的內(nèi)容
和上面的程序比，只需要多一個(gè)二維數(shù)組記錄在遍歷中所選擇的子問題的最優(yōu)解即可。如下程序：
?
[cpp]?view plain?copy
//輸出最長(zhǎng)公共子串（LCS）??//二維數(shù)組veca記錄的是兩個(gè)字符串Xi和Yj的LCS長(zhǎng)度??int?LCS_length(const?string?&str1,?const?string?&str2,???????????????????vector<vector<int>?>?&veca,?vector<vector<int>?>?&vecb)?{??????int?i,?j;??????int?biggest?=?0;??????if?(str1?==?""?||?str2?==?"")??????????return?0;????????for?(i?=?0;?i?<=?str1.length();?i++)?{??????????veca[i][0]?=?0;??????}??????for?(j?=?0;?j?<=?str2.length();?j++)?{??????????veca[0][j]?=?0;??????}??????for?(i?=?1;?i?<=?str1.length();?i++)?{??????????for?(j?=?1;?j?<=?str2.length();?j++)?{??????????????//如果Xi-1?==?Yj-1，那么最長(zhǎng)子序列為veca[i?-?1][j?-?1]?+?1??????????????//此時(shí)將vecb[i][j]?=?1表明str1[i-1]是子問題LCS的一個(gè)元素??????????????if?(str1[i?-?1]?==?str2[j?-?1])?{??????????????????veca[i][j]?=?veca[i?-?1][j?-?1]?+?1;??????????????????vecb[i][j]?=?1;??????????????}??????????????else?{??????????????????if?(veca[i?-?1][j]?>=?veca[i][j?-?1])?{??????????????????????veca[i][j]?=?veca[i?-?1][j];??????????????????????vecb[i][j]?=?2;??????????????????}??????????????????else?{??????????????????????veca[i][j]?=?veca[i][j-1];??????????????????????vecb[i][j]?=?3;??????????????????}??????????????}??????????}??????}??????return?veca[str1.length()][str2.length()];??}????//該函數(shù)用于輸出一個(gè)LCS的序列??//這里輸出的順序是先向上尋找，再向左尋找??void?PrintOneLCS(vector<vector<int>?>?&vecb,?string?&str1,?int?i,?int?j)?{??????if?(i?==?0?||?j?==?0)??????????return;??????if?(vecb[i][j]?==?1)?{??????????PrintOneLCS(vecb,?str1,?i?-?1,?j?-?1);??????????cout?<<?str1[i?-?1]?<<?"?";??????}??????else?if?(vecb[i][j]?==?2)??????????PrintOneLCS(vecb,?str1,?i?-1,?j);??????else??????????PrintOneLCS(vecb,?str1,?i,?j?-?1);??}????int?main()?{??????string?input;??????getline(cin,?input);??????stringstream?ss(input);??????string?str1,?str2;??????ss?>>?str1;??????ss?>>?str2;??????//將veca初始化為一個(gè)二維數(shù)組,其行列值分別為str1和str2的長(zhǎng)度加1??????//二維數(shù)組veca記錄的是兩個(gè)字符串Xi和Yj的LCS長(zhǎng)度??????//二維數(shù)組vecb[i][j]記錄veca[i][j]時(shí)所選擇的子問題的最優(yōu)解??????vector<vector<int>?>?veca(str1.length()?+?1,?vector<int>(str2.length()?+?1));??????vector<vector<int>?>?vecb(str1.length()?+?1,?vector<int>(str2.length()?+?1));??????cout?<<?LCS_length(str1,?str2,?veca,?vecb)?<<?endl;??????PrintOneLCS(vecb,?str1,?str1.length(),?str2.length());??????return?0;??}??
?
求一個(gè)LCS內(nèi)容也可以不借助輔助二維數(shù)組vecb而是用下面小節(jié)的方法，
[cpp]?view plain?copy
//該函數(shù)用于輸出一個(gè)LCS的序列，使用下一小節(jié)的方法??//這里輸出的順序是先向左尋找，再向上尋找??void?PrintOneLCS(string?&str1,?string?&str2,?int?i,?int?j,???????vector<vector<int>?>?&veca)?{??????????string?lcs_str;??????????while?(i?>?0?&&?j?>?0)?{??????????????if?(str1[i?-?1]?==?str2[j?-?1])?{??????????????????lcs_str?=?str1[i?-?1]?+?lcs_str;??????????????????--i;??????????????????--j;??????????????}??????????????else?{??????????????????//如果左邊存在LCS就從左邊找否則再?gòu)挠疫呎??????????????????if?(veca[i?-?1][j]?>=?veca[i][j?-?1])??????????????????????--i;??????????????????else??????????????????????--j;??????????????}??????????}??????????cout?<<?lcs_str?<<?endl;??}??
如下代碼：
?
?
要輸出所有LCS的內(nèi)容
兩個(gè)字符串對(duì)應(yīng)的最長(zhǎng)公共子序列不一定唯一，這個(gè)程序輸出所有的LCS內(nèi)容。
基本思想是：
具體參考文章：http://blog.csdn.net/lisonglisonglisong/article/details/41596309
代碼：
?
[cpp]?view plain?copy
#include?<vector>??#include?<iomanip>??#include?<set>??#include?<string>??#include?<map>??#include?<iostream>??#include?<string.h>??#include?<sstream>??using?namespace?std;????set<string>?all_lcs;?//注意這里要用set去除重復(fù)的LCS??//最長(zhǎng)公共子串（LCS）??//二維數(shù)組veca[i][j]記錄的是兩個(gè)字符串Xi和Yj的LCS長(zhǎng)度??int?LCS_length(const?string?&str1,?const?string?&str2,?vector<vector<int>?>?&veca)?{??????int?i,?j;??????int?biggest?=?0;??????if?(str1?==?""?||?str2?==?"")??????????return?0;????????for?(i?=?0;?i?<=?str1.length();?i++)?{??????????veca[i][0]?=?0;??????}??????for?(j?=?0;?j?<=?str2.length();?j++)?{??????????veca[0][j]?=?0;??????}??????for?(i?=?1;?i?<=?str1.length();?i++)?{??????????for?(j?=?1;?j?<=?str2.length();?j++)?{??????????????if?(str1[i?-?1]?==?str2[j?-?1])?{??????????????????veca[i][j]?=?veca[i?-?1][j?-?1]?+?1;??????????????}??????????????else?{??????????????????if?(veca[i?-?1][j]?>=?veca[i][j?-?1])??????????????????????veca[i][j]?=?veca[i?-?1][j];??????????????????else??????????????????????veca[i][j]?=?veca[i][j-1];??????????????}??????????}??????}??????return?veca[str1.length()][str2.length()];??}????//該函數(shù)找出所有的LCS的序列，并將其存在vector中??void?PrintAllLCS(string?&str1,?string?&str2,?int?i,?int?j,????????????????????vector<vector<int>?>?&veca,?string?lcs_str)?{??//注意這里形參lcs_str不可以為引用，這里需要每次調(diào)用lcs_str都重新生成一個(gè)對(duì)象??????while?(i?>?0?&&?j?>?0)?{??????????if?(str1[i?-?1]?==?str2[j?-?1])?{??????????????lcs_str?=?str1[i?-?1]?+?lcs_str;?//逆向存放??????????????--i;??????????????--j;??????????}??????????else?{??????????????if?(veca[i?-?1][j]?>?veca[i][j?-?1])?//向左走??????????????????--i;??????????????else?if?(veca[i?-?1][j]?<?veca[i][j?-?1])?//向上走??????????????????--j;??????????????else?{?//此時(shí)向上向右均為L(zhǎng)CS的元素??????????????????PrintAllLCS(str1,?str2,?i?-?1,?j,?veca,?lcs_str);??????????????????PrintAllLCS(str1,?str2,?i,?j?-?1,?veca,?lcs_str);??????????????????return;??????????????}??????????}??????}??????cout?<<?"???"?<<?lcs_str?<<?endl;??????all_lcs.insert(lcs_str);??}??int?main()?{??????string?input;??????getline(cin,?input);??????stringstream?ss(input);??????string?str1,?str2;??????ss?>>?str1;??????ss?>>?str2;??????//將veca初始化為一個(gè)二維數(shù)組,其行列值分別為str1和str2的長(zhǎng)度加1??????//二維數(shù)組veca記錄的是兩個(gè)字符串Xi和Yj的LCS長(zhǎng)度??????vector<vector<int>?>?veca(str1.length()?+?1,?vector<int>(str2.length()?+?1));??????cout?<<?LCS_length(str1,?str2,?veca)?<<?endl;????????string?lcs_str;??????PrintAllLCS(str1,?str2,?str1.length(),?str2.length(),?veca,?lcs_str);??????set<string>::iterator?iter?=?all_lcs.begin();??????while?(iter?!=?all_lcs.end())?{??????????cout?<<?*iter++?<<?endl;??????}??????return?0;??}??
?
如圖所示的兩個(gè)字符串共有三個(gè)LCS。
二、最長(zhǎng)公共子串
描述：
計(jì)算兩個(gè)字符串的最大公共子串（Longest Common Substring）的長(zhǎng)度，字符不區(qū)分大小寫。
輸入：
輸入兩個(gè)字符串
輸出：
輸出一個(gè)整數(shù)
樣例輸入：
asdfas werasdfaswer
樣例輸出：
6
?
這里的最大公共字串要求的字串是連續(xù)的。
求字串的方法和求子序列方法類似：
當(dāng)str1[i] == str2[j]時(shí)，子序列長(zhǎng)度veca[i][j] = veca[i - 1][j - 1] + 1；只是當(dāng)str1[i] ！= str2[j]時(shí)，veca[i][j]長(zhǎng)度要為0，而不是max{veca[i - 1][j], veca[i][j - 1]}。
?
[cpp]?view plain?copy
#include?<vector>????#include?<string>????#include?<iostream>????#include?<string.h>????#include?<sstream>????using?namespace?std;????????int?LCS_length(const?string?&str1,?const?string?&str2,?vector<vector<int>?>?&veca)?{????????int?i,?j;????????int?biggest?=?0;????????if?(str1?==?""?||?str2?==?"")????????????return?0;????????for?(i?=?0;?i?<=?str1.length();?i++)?{????????????veca[i].resize(str2.length()?+?1,?0);????????}????????for?(j?=?0;?j?<=?str2.length();?j++)?{????????????veca[0][j]?=?0;????????}????????for?(i?=?1;?i?<=?str1.length();?i++)?{????????????for?(j?=?1;?j?<=?str2.length();?j++)?{????????????????if?(str1[i?-?1]?==?str2[j?-?1])?{????????????????????veca[i][j]?=?veca[i?-?1][j?-?1]?+?1;????????????????????if?(veca[i][j]?>?biggest)????????????????????????biggest?=?veca[i][j];????????????????}????????????????else???????//可以看出，求最長(zhǎng)子串和求最長(zhǎng)子序列差別僅僅在這里??????????????????veca[i][j]?=?0;????????????????????????????}????????}????????return?biggest;????}????????int?main()?{????????string?input;????????getline(cin,?input);????????stringstream?ss(input);????????string?str1;????????ss?>>?str1;????????string?str2;????????ss?>>?str2;????????vector<vector<int>?>?veca(str1.length()?+?1);????????cout?<<?LCS_length(str1,?str2,?veca)?<<?endl;????????return?0;????}????
同樣適用求最長(zhǎng)子序列的測(cè)試數(shù)據(jù)，得到它們的公共最長(zhǎng)子串長(zhǎng)度為2，而它們的公共最長(zhǎng)子序列長(zhǎng)度為4.
?
?
三、動(dòng)態(tài)規(guī)劃的其它題目
1、硬幣面值組合問題
http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html
?
2、最長(zhǎng)遞增子序列
? ? ? ? ? ?除了動(dòng)態(tài)規(guī)劃，該題還有其他解法。
?
3、數(shù)組最大子數(shù)組和的最大值
http://www.ahathinking.com/archives/120.html
?
3、動(dòng)態(tài)規(guī)劃之鋼條分割
?
4、計(jì)算兩個(gè)字符串的相似度（編程之美）
? ? ? ?該文章原理說得比較清楚：點(diǎn)擊打開鏈接
? ? ? ?這里是代碼：點(diǎn)擊打開鏈接
?
5、求每一對(duì)頂點(diǎn)之間的最短路徑：Floyd-Warshall算法
?
轉(zhuǎn)自：https://blog.csdn.net/u013074465/article/details/45392687
總結(jié)
以上是生活随笔為你收集整理的动态规划算法---求最长公共子序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
