LCS アルゴリズム & 最大共通部分文字列 & 最長共通部分列 PHP 実装 最長共通増加部分列 最長共通部分列 C 言語 最長共通増加部分列

2 つの文字列の最大共通部分文字列と最長共通部分列を見つけます

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

<code>4</code>

つまり、bdcaba と abcbdab の最大共通部分文字列長は 4 です bdcaba 与 abcbdab 的最大公共子串长度为 4

常规思路

枚举法，算出两个字符串的所有子序列，然后分别作比较，选出最大的一个子串

缺点：对于一个长度为 n 的字符串，子串个数有 2 的 n 次方个，然后在依次比较两个字符串的子串，效率过低

动态规划 LCS算法

以动态规划的思想来解这个题，我们用一个二位数组 $dp[][]

従来idea

Enumeration メソッドでは、2 つの文字列のすべての部分列を計算し、それらを個別に比較して最大の部分文字列を選択します

欠点: 長さ n の文字列の場合、部分文字列の数は 2 の n 乗となり、 2 つの文字列の部分文字列を順番に並べるのは非効率すぎます

動的計画法 LCS アルゴリズム

動的計画法の考え方でこの問題を解決するには、2 桁の配列 $dp[][] を使用します。 は各文字列に対応するステータスを格納します。具体的な意味については詳しく説明しません。Baidu で検索していただければわかりますが、主に 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) に削減されますが、一部のデータのストレージは不要であり、スペースの無駄がまだあります。さらに最適化できます 🎜🎜🎜').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i 🎜').text(i)); }; $numbering.fadeIn(1700); }); }); 🎜 🎜 上記は、最長共通部分列と PHP コンテンツを含む、LCS アルゴリズム、最大共通部分文字列、および最長共通部分列の PHP 実装を紹介しています。PHP チュートリアルに興味のある友人に役立つことを願っています。 🎜 🎜 🎜