LCS 알고리즘 및 최대 공통 부분 문자열 및 가장 긴 공통 부분 수열 PHP 구현 가장 긴 공통 증가 부분 수열 가장 긴 공통 부분 수열 c 언어 가장 긴 공통 증가 부분 수열

두 문자열

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

<code>4</code>

, 즉 bdcaba과 abcbdab의 가장 큰 공통 부분 문자열과 가장 큰 공통 부분 문자열을 찾습니다. 길이는 4

기존 아이디어

열거 방법, 두 문자열의 모든 하위 시퀀스를 계산한 다음 각각 비교하고 가장 큰 하위 문자열을 선택

단점: 길이가 n인 문자열의 경우 하위 문자열 개수가 2의 n제곱이므로 두 문자열의 하위 문자열을 순서대로 비교하는 것은 너무 비효율적입니다

동적 프로그래밍 LCS 알고리즘

는 이 문제를 해결하기 위해 동적 프로그래밍 아이디어를 사용합니다. 각 문자열에 해당하는 상태를 저장하기 위해 두 자리 배열 $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); }); });

위 내용은 LCS 알고리즘의 PHP 구현과 가장 긴 공통 부분 문자열 및 PHP 콘텐츠를 포함하는 가장 큰 공통 부분 문자열을 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.