두 문자열
<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>
').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });결론: 동적 프로그래밍을 통해 시간 복잡도를 O(nm)로 줄였지만, 이 폐기물을 위한 공간은 여전히 남아 있으며, 일부 데이터 저장은 불필요하며 더욱 최적화될 수 있습니다
위 내용은 LCS 알고리즘의 PHP 구현과 가장 긴 공통 부분 문자열 및 PHP 콘텐츠를 포함하는 가장 큰 공통 부분 문자열을 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.