Home Backend Development PHP Tutorial PHP algorithm: PHP implements the problem of the longest common substring

PHP algorithm: PHP implements the problem of the longest common substring

Oct 18, 2018 pm 03:35 PM
php php algorithm longest common substring

What this article brings to you is the problem of the longest common substring in PHP implementation of the PHP algorithm. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Longest common substring problem:

Given two strings, find the length of the longest identical substring between them.

Violent solution ideas:

1. Start with each character of the two strings and compare them later, which will require two levels of loops

2. The comparison method inside the two-level loop is also a one-level loop, starting from the current character, traversing and comparing until there is a difference, then jump out of the loop and record the length of the same substring

3. Based on the longest length, there are three levels of loops. Time complexity O(n^3)

longest=0
for i=0;i<str1.size;i++
    for j=0;j<str2.size;j++
        m=i  n=j length=0
    while(m<str1.size && n<str2.size)
            if str1[m]!=str2[n] break
            ++length
            ++m
            ++n
        longest=longest<length ? length:longest
Copy after login

Dynamic programming method:

1. In the above comparison process, starting from i and j, if After reaching a different stop, the next starting position will be compared repeatedly

2. Dynamic programming method-space for time, matrix graph, can reduce the complexity to O(n^2)

3.str1 is the horizontal axis, str2 is the vertical axis, table[i][j] is the length of the longest substring ending with these two characters

4.table[0][j] It can be deduced, if str1[0]==str2[j] is 1, table[i][0] can be deduced, if str1[i]==str2[0] is 1, and the rest is 0

5.table[i][j] If str1[i]==str2[j] can be obtained from table[i-1][j-1] 1, if not equal to 0

Assume that the two strings are s and t respectively, s[i] and t[j] represent the i-th and j-th characters respectively (the character order starts from 0), and then let L[i, j] represent s[ i] and s[j] are the maximum length of the same substring at the end. It should not be difficult to derive the relationship between L[i, j] and L[i 1,j 1], because the only difference between the two is the pair of characters s[i 1] and t[j 1]. If s[i 1] and t[j 1] are different, then L[i 1, j 1] should naturally be 0, because any substring ending with them cannot be exactly the same; and if s[i 1] The same as t[j 1], then just add these two characters after the longest identical substring ending with s[i] and t[j], so that the length can be increased by one. Combining the above two situations, we get the relationship L[i 1,j 1]=(s[i]==t[j]?L[i,j] 1:0).

Code example:

<?php
$str1="abcdef";
$str2="esdfdbcde1";

//暴力解法
function longestCommonSubstring1($str1,$str2){
        $longest=0;
        $size1=strlen($str1);
        $size2=strlen($str2);
        for($i=0;$i<$size1;$i++){
                for($j=0;$j<$size2;$j++){
                        $m=$i;
                        $n=$j;
                        $length=0;
                        while($m<$size1 && $n<$size2){
                                if($str1[$m]!=$str2[$n]) break;
                                ++$length;
                                ++$m;
                                ++$n;
                        }   
                        $longest=$longest < $length ? $length : $longest;
                }   
        }   
        return $longest;
}
//矩阵动态规划法
function longestCommonSubstring2($str1,$str2){
        $size1=strlen($str1);
        $size2=strlen($str2);
        $table=array();
        for($i=0;$i<$size1;$i++){
                $table[$i][0]=$str1[$i]==$str2[0] ? 1:0;
        }   
        for($j=0;$j<$size2;$j++){
                $table[0][$j]=$str1[0]==$str2[$j] ? 1:0;
        }   
        for($i=1;$i<$size1;$i++){
                for($j=1;$j<$size2;$j++){
                        if($str1[$i]==$str2[$j]){
                                $table[$i][$j]=$table[$i-1][$j-1]+1;    
                        }else{
                                $table[$i][$j]=0;
                        }    
                }   
        }   
        $longest=0;
        for($i=0;$i<$size1;$i++){
                for($j=0;$j<$size2;$j++){
                        $longest=$longest<$table[$i][$j] ? $table[$i][$j] : $longest;
        }}  
        return $longest;
}
$len=longestCommonSubstring1($str1,$str2);
$len=longestCommonSubstring2($str1,$str2);
var_dump($len);
Copy after login

The above is the entire content of this article. For more related tutorials, please visit php programming from entry to master full set of video tutorials, php practical video tutorial, bootstrap video tutorial!

The above is the detailed content of PHP algorithm: PHP implements the problem of the longest common substring. For more information, please follow other related articles on the PHP Chinese website!

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

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian

CakePHP Date and Time CakePHP Date and Time Sep 10, 2024 pm 05:27 PM

CakePHP Date and Time

CakePHP Project Configuration CakePHP Project Configuration Sep 10, 2024 pm 05:25 PM

CakePHP Project Configuration

CakePHP File upload CakePHP File upload Sep 10, 2024 pm 05:27 PM

CakePHP File upload

CakePHP Routing CakePHP Routing Sep 10, 2024 pm 05:25 PM

CakePHP Routing

Discuss CakePHP Discuss CakePHP Sep 10, 2024 pm 05:28 PM

Discuss CakePHP

CakePHP Quick Guide CakePHP Quick Guide Sep 10, 2024 pm 05:27 PM

CakePHP Quick Guide

How To Set Up Visual Studio Code (VS Code) for PHP Development How To Set Up Visual Studio Code (VS Code) for PHP Development Dec 20, 2024 am 11:31 AM

How To Set Up Visual Studio Code (VS Code) for PHP Development

See all articles