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
1353 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.

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!