LCS演算法&最大公共子序列&最長公共子序列 PHP 實作最長公共上升子序列最長公共子序列c語言最長公共遞增子序-php教程-PHP中文網

LCS演算法&最大公共子序列&最長公共子序列 PHP 實作最長公共上升子序列最長公共子序列c語言最長公共遞增子序

WBOY

發布： 2016-07-29 08:54:24

原創

1399 人瀏覽過

求兩個字串的最大公共子字串&最長公共子序列

<code>输入：
abcbdab
bdcaba</code>

登入後複製

<code>4</code>

登入後複製

即bdcaba 與abcbdab 的最大公共子串長度為4
abcbdab

兩個字串的所有子序列，然後分別作比較，選出最大的一個子字串

缺點：對於一個長度為n 的字串，子串個數有2 的n 次方個，然後在依次比較兩個字串的子字串，效率過低

動態規劃LCS演算法

以動態規劃的思想來解這個題，我們用一個二位數組

$dp[][]

來儲存各個字串對應的狀態，具體什麼意義就不細說了，百度一下，你就知道，主要是用PHP 實作一下程式碼如下：

<code><span><span>function</span><span>lcs</span><span>(<span>$str1</span>, <span>$str2</span>)</span>
{</span><span>// 存储生成的二维矩阵</span><span>$dp</span> = <span>array</span>();
    <span>// 最大子串长度</span><span>$max</span> = <span>0</span>;

    <span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < strlen(<span>$str1</span>); <span>$i</span>++) { 
        <span>for</span> (<span>$j</span> = <span>0</span>; <span>$j</span> < strlen(<span>$str2</span>); <span>$j</span>++) { 
            <span>if</span> (<span>$str1</span>[<span>$i</span>] == <span>$str2</span>[<span>$j</span>]) {
                <span>$dp</span>[<span>$i</span>][<span>$j</span>] = <span>isset</span>(<span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>-<span>1</span>]) ? <span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>-<span>1</span>] + <span>1</span> : <span>1</span>;
            } <span>else</span> {
                <span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>] = <span>isset</span>(<span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>]) ? <span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>] : <span>0</span>;
                <span>$dp</span>[<span>$i</span>][<span>$j</span>-<span>1</span>] = <span>isset</span>(<span>$dp</span>[<span>$i</span>][<span>$j</span>-<span>1</span>]) ? <span>$dp</span>[<span>$i</span>][<span>$j</span>-<span>1</span>] : <span>0</span>;

                <span>$dp</span>[<span>$i</span>][<span>$j</span>] = <span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>] > <span>$dp</span>[<span>$i</span>][<span>$j</span>-<span>1</span>] ? <span>$dp</span>[<span>$i</span>-<span>1</span>][<span>$j</span>] : <span>$dp</span>[<span>$i</span>][<span>$j</span>-<span>1</span>];
            }

            <span>$max</span> = <span>$dp</span>[<span>$i</span>][<span>$j</span>] > <span>$max</span> ? <span>$dp</span>[<span>$i</span>][<span>$j</span>] : <span>$max</span>;
        }
    }

    <span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < strlen(<span>$str1</span>); <span>$i</span>++) { 
        <span>for</span> (<span>$j</span> = <span>0</span>; <span>$j</span> < strlen(<span>$str2</span>); <span>$j</span>++) { 
            <span>echo</span><span>$dp</span>[<span>$i</span>][<span>$j</span>] . <span>" "</span>;
        }
        <span>echo</span><span>"<br />";
    }

    var_dump(<span>$max</span>);
}

lcs(<span>"abcbdab"</span>, <span>"bdcaba"</span>);</code>

登入後複製

對應輸出：

<code><span>0</span><span>0</span><span>0</span><span>1</span><span>1</span><span>1</span><span>1</span><span>1</span><span>1</span><span>1</span><span>2</span><span>2</span><span>1</span><span>1</span><span>2</span><span>2</span><span>2</span><span>2</span><span>1</span><span>1</span><span>2</span><span>2</span><span>3</span><span>3</span><span>1</span><span>2</span><span>2</span><span>2</span><span>3</span><span>3</span><span>1</span><span>2</span><span>2</span><span>3</span><span>3</span><span>4</span><span>1</span><span>2</span><span>2</span><span>3</span><span>4</span><span>4</span><span>int</span><span>4</span></code>

登入後複製

結論：透過動態規劃，我們讓時間複雜度降為了O(nm)，但是這樣依舊有空間的浪費，有些資料的儲存是不必要的，可以進一步做最佳化