Find the largest common substring & longest common subsequence of two strings
<code>输入: abcbdab bdcaba</code>
<code>4</code>
That is, the maximum common substring length of
bdcaba
andabcbdab
is 4
Conventional ideas
enumeration method, calculate All subsequences of the two strings are then compared separately to select the largest substring
Disadvantages: For a string of length n, the number of substrings is 2 to the nth power, and then in sequence Comparing substrings of two strings is too inefficient
Dynamic programming LCS algorithm
Using the idea of dynamic programming to solve this problem, we use a two-digit array$dp[][]
to store each string I won’t elaborate on the specific meaning of the corresponding status. Just search it on Baidu and you will know. It is mainly implemented using PHP
The code is as follows:
<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>
Corresponding output:
<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); }); });Conclusion: Through dynamic programming, we reduce the time complexity to O(nm), but there is still a waste of space. The storage of some data is unnecessary and can be further Optimize
The above introduces the PHP implementation of the LCS algorithm & largest common substring & longest common subsequence, including the longest common subsequence and PHP content. I hope it will be helpful to friends who are interested in PHP tutorials.