LCS algorithm & largest common substring & longest common subsequence PHP implementation longest common increasing subsequence longest common subsequence c language longest common increasing subsequence-PHP Tutorial-php.cn

LCS algorithm & largest common substring & longest common subsequence PHP implementation longest common increasing subsequence longest common subsequence c language longest common increasing subsequence

WBOY

Release： 2016-07-29 08:54:24

Original

1355 people have browsed it

Find the largest common substring & longest common subsequence of two strings

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

Copy after login

<code>4</code>

Copy after login

That is, the maximum common substring length of bdcaba and abcbdab 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>

Copy after login

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>

Copy after login

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

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });

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.