動態規劃問題（2）——尋找最長公共子串

wushuiyong 發布于2019-08-21 11:27 / 3022人閱讀

摘要：題目給定兩個字符串求出它們的最長公共字串說明比如在單詞和它們的最長公共子序列是。最長公共子串和最長公共子序列的區別。

題目

給定兩個字符串,求出它們的最長公共字串

var str1="abcdefg";
var str2="xyzabcd";

說明：比如在單詞"abcdefg"和"abcdefg"它們的最長公共子序列是"abcd"。尋找最長子序列常用于遺傳學中，用于使用核苷酸堿基的首字母對DNA的描述（這段話從網上抄的）。

最長公共子串和最長公共子序列的區別。

最長公共子串和最長公共子序列的區別為：子串是串的一個連續的部分，子序列則是從不改變序列的順序，而從序列中去掉任意的元素而獲得新的序列；也就是說，子串中字符的位置必須是連續的，子序列則可以不必連續。

這道題，想了很長時間，終于慢慢的把題目做出來了，接下來的內容可能會很難理解，也許我比較笨吧至少對我來說想了好久。我會盡量結合圖文去展示解題的思路，也可以自己想想，然后在看接下來的內容。

暴力破解

其實看到這個問題我們直接可以用暴力的方式解決這個問題。給定兩個字符串A和B，我們可以通過從A的第一個字符開始與B對應的每一個字符進行對比的方式找到最長的公共字串。如果此時沒有找到匹的字母，則移動到A的第二個字符處，然后從B的第一個字符處進行對比，以此類推。由于下面的內容較多，爆力方法我這里就不寫了。

動態規劃

我們回顧一下動態規劃的解題思路：

從底部開始解決問題，將所有小問題解決掉，然后合并成一個整體的解決方案。

使用一個數組建立一張表，用于存放被分解成眾多子問題的解。

那基于這兩點我們首先要分解這個問題，怎么分解呢？

第一步： 最小的是每個字符，所以要把分解成單個的字符去匹配每個單個的字符。因此這里我們可以得到下面這一張表：

匹配為1，不匹配為0，這個時候我們就分解成為每個字符的匹配情況，由此得到。

第二步： 每個子問題有了，這個時候我們要建立一個數組去存放每個子問題的解。關鍵問題在于，我們怎么樣把每個子問題的解存起來，并且可以得到我們想要的結果。對表做一些處理，初始化一個二維數組：

var arr = new Array(str1.length + 1);
for (var i = 0; i <= str1.length + 1; i++) {
    arr[i] = new Array(str2.length + 1);
    for (var j = 0; j <= str2.length + 1; j++) {
        arr[i][j] = 0;
    }
}

得到如下的表：

圖中我們可以看到行和列都多加了一個并且都是0，這是為了判斷上一個是否相等的操作，后面你就會明白它的意思了。

對初始化的二維數組坐些處理，得到如下圖：

一開始看到這個圖的時候你可能會很懵逼，如果你已經看明白了，那你就跳過我這段廢話吧。我們應該一直的告訴自己，新建的這個數組是存放每個子問題的解，首先要明確的是找出最長字串，有哪些方式可以做到把字串從原來的字符串中截取，所以要知道起始位置和字串的長度。從圖中可以看到的紅字就是存放這個位置的最優解字串的長度，所以應該建立兩個變量去存儲其實位置的index 和最大長度 maxLen 。得到一下代碼：

var maxLen = 0;
var index = 0;
for(var i = 0; i <= str1.length; i++){
    for(var j = 0; j <= str2.length; j++){
        if(i == 0 || j == 0){
            arr[i][j] = 0
        }else{
            if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }else{
                arr[i][j] = 0;
            }
        }
        if(arr[i][j] > maxLen){
            maxLen = arr[i][j];
            index = i;
        }
    }
}

簡單的解釋一下，這里要明確連續的字串的位置，是二維數組對角線上的值，這點明確了很多問題就好理解了。

上面的代碼把最主要的兩個參數找到了，那接下來就是選擇其中的一個字符串去截取字串：

var str = "";
if(maxLen == 0){
    return "";
}else{
    for(var k = index - maxLen; k < maxLen; k++){
        str += str1[k];
    }
    return str;
}

下面貼上完整的代碼，你也可以去我的github上查看源碼；

function LCS(str1, str2){
    var maxLen = 0;
    var index = 0;

    var arr = new Array();
    for (var i = 0; i <= str1.length + 1; i++) {
        arr[i] = new Array();
        for (var j = 0; j <= str2.length + 1; j++) {
            arr[i][j] = 0;
        }
    }

    for(var i = 0; i <= str1.length; i++){
        for(var j = 0; j <= str2.length; j++){
            if(i == 0 || j == 0){
                arr[i][j] = 0
            }else{
                if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                }else{
                    arr[i][j] = 0;
                }
            }
            if(arr[i][j] > maxLen){
                maxLen = arr[i][j];
                index = i;
            }
        }
    }

    var str = "";
    if(maxLen == 0){
        return "";
    }else{
        for(var k = index - maxLen; k < maxLen; k++){
            str += str1[k];
        }
        return str;
    }
}
var str1="abcdefg";
var str2="xyzabcd";
LCS(str1, str2)     // abcd

到此為止我們終于找到了最長公共字串。到這里我們需要想想能不能在優化了，雖然這樣解決問題，但是引入了一個二維數組，在兩個字符串都較大的情況下不是很劃算，是否可以進一步優化？答案是可以的，需要改變一下策略，是否可以建立一個一維數組就可以解決問題了呢，這里晚了先寫這么多把，之后我會在公眾號中貼出暴力解法和動態規劃的優化解法，歡迎持續關注我的公眾號獲得一手的信息。

歡迎關注微信公眾賬號查看最新文章

GPU云服務器云服務器最長公共子串 java最長相同子串最長公共子序列 java公共子串

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/86727.html

[算法筆記]動態規劃之最長公共子串和最長公共子序列

摘要：源代碼管理中，指令，可以查找出編輯前后文件的差異，這是基于動態規劃實現的。編輯距離，判斷字符串的相似程度，也是基于動態規劃計算。本文是《算法圖解》筆記應用場景一切脫離實際應用場景的算法都是耍流氓！生物學家根據最長公共序列來確定 DNA 鏈的相似性，進而判斷兩種動物或疾病有多相似。最長公共序列還被用來尋找多發性硬化癥治療方案。源代碼管理中，git diff指令，可以查找出編輯...

DandJ 2019-07-30 15:40 評論0 收藏0
算法設計 - LCS 最長公共子序列&&最長公共子串 &&LIS 最

摘要：若且，則是和的最長公共子序列若且，則是和的最長公共子序列。遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算和的最長公共子序列時，可能要計算出和及和的最長公共子序列。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨本章講解： 1. LCS（最長公共子序列）O(n^2)的時間復雜...

weizx 2019-08-14 12:07 評論0 收藏0
字符串處理文章outline

摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關于字符串的文章的怎么翻譯匯集目錄非常希望強化博客的功能，比如分類，置頂。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨最近在看算法和語言，基本屬于看知識 --> java實現 --> 整理blog 這個路線。遇到問題查查st...

Karuru 2019-08-14 15:07 評論0 收藏0
動態規劃法（十）最長公共子序列（LCS）問題

摘要：最長公共子序列問題指的是求解兩個序列和的長度最長的公共子序列。當然，可以看出，問題容易出現重疊子問題，這時候，就需要用動態規劃法來解決。問題介紹 ??給定一個序列$X=$，另一個序列$Z=$滿足如下條件時稱為X的子序列：存在一個嚴格遞增的X的下標序列${i_1,i_2,...,i_k}$，對所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$??給定兩個序列$X$和$Y$...

Ashin 2019-08-15 18:17 評論0 收藏0
動態規劃法（十）最長公共子序列（LCS）問題

摘要：最長公共子序列問題指的是求解兩個序列和的長度最長的公共子序列。當然，可以看出，問題容易出現重疊子問題，這時候，就需要用動態規劃法來解決。問題介紹 ??給定一個序列$X=$，另一個序列$Z=$滿足如下條件時稱為X的子序列：存在一個嚴格遞增的X的下標序列${i_1,i_2,...,i_k}$，對所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$??給定兩個序列$X$和$Y$...

IamDLY 2019-07-30 16:49 評論0 收藏0