PHP 알고리즘: PHP는 가장 긴 공통 부분 문자열 문제를 구현합니다.

이 기사에서 제공하는 내용은 PHP 알고리즘에서 가장 긴 공통 하위 문자열의 PHP 구현 문제입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

가장 긴 공통 부분 문자열 문제:

두 개의 문자열이 주어졌을 때, 두 문자열 사이에서 가장 긴 동일한 부분 문자열의 길이를 구하세요.

폭력적인 해결책 아이디어:

1. 두 문자열의 각 문자로 시작하여 나중에 비교합니다. 이를 위해서는 두 수준의 루프가 필요합니다.

2. 2단계 루프 내부의 비교 방법도 1단계 루프입니다. , 현재 문자부터 시작하여 차이가 있을 때까지 순회하고 비교한 다음 루프에서 벗어나 동일한 하위 문자열의 길이를 기록합니다

3. 가장 긴 길이가 우선하므로 세 가지 수준의 루프가 있습니다. 시간 복잡도 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

동적 프로그래밍 방법:

1 위의 비교 과정에서 i와 j부터 시작하여 서로 다른 정지점을 만나면 다음 시작 위치는 반복 비교

2입니다. 동적 프로그래밍 방법 - 시간에 대한 공간, 행렬 그래프는 복잡성을 O(n^2)

3으로 줄일 수 있습니다.str1은 가로 축, str2는 세로 축, table[i][j ]는 길이입니다. str1[0]==str2[j]가 1이면 table[i][ 0]은 str1이면 추론할 수 있습니다. [i]==str2[0]은 1이고 나머지는 0

5.table[i][j] str1[i]==str2[j]를 table[i -1][로 계산할 수 있는 경우 j-1]+1을 구하고, 같지 않으면 0

두 문자열이 각각 s와 t라고 가정하고, s[i]와 t[j]는 각각 i번째와 j번째 문자를 나타냅니다( 문자 순서는 0부터 시작), L[i, j]는 s[i] 및 s[j]로 끝나는 동일한 하위 문자열의 최대 길이를 나타냅니다. L[i, j]와 L[i+1,j+1] 사이의 관계를 추론하는 것은 어렵지 않습니다. 둘 사이의 유일한 차이점은 문자 쌍 s[i+1]과 t[j이기 때문입니다. +1] . s[i+1]과 t[j+1]이 다르면 L[i+1, j+1]은 당연히 0이 되어야 합니다. 왜냐하면 이들로 끝나는 부분 문자열은 정확히 동일할 수 없고 s [i인 경우에도 마찬가지입니다. +1]과 t[j+1]은 동일합니다. 그런 다음 s[i] 및 t[j]로 끝나는 가장 긴 동일한 하위 문자열 뒤에 이 두 문자를 추가하면 길이가 한 명 더 추가됩니다. 위의 두 가지 상황을 결합하면 L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0) 관계를 얻습니다.

코드 예:

<?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);

위는 이 기사의 전체 내용입니다. 더 많은 관련 튜토리얼을 보려면

php 프로그래밍 초보부터 마스터까지 전체 비디오 튜토리얼 세트

, php 실용 비디오 튜토리얼, bootstrap을 방문하세요. 비디오 튜토리얼!

위 내용은 PHP 알고리즘: PHP는 가장 긴 공통 부분 문자열 문제를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!