PHP アルゴリズム: PHP は最長共通部分文字列の問題を実装します。

この記事がもたらすのは、PHP アルゴリズムの PHP 実装における最長の共通部分文字列の問題です。一定の参考値があるので、困っている友達は参考にしていただければ幸いです。

最長共通部分文字列問題:

2 つの文字列が与えられた場合、それらの間で最も長い同一部分文字列の長さを見つけます。

暴力的な解決策のアイデア:

1. 2 つの文字列の各文字から始めて、後で比較します。これには 2 レベルのループが必要です

2. 2 レベルのループ内の比較方法は 1 レベルのループでもあり、現在の文字から開始して、差異が見つかるまでトラバースして比較し、その後ループから抜け出して同じ部分文字列の長さを記録します

3. 最長の長さに基づいて、ループには 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] はこれら 2 つの文字で終わる最長の部分文字列の長さです。

4.table[0][j] str1[0]==str2[j] は 1、str1[i]==str2[0] が 1、残りが 0

5 であれば、table[i][0] を推定できます。 .table[i][j] str1[i]==str2[j] が table[i-1][j-1] 1 から取得できる場合、0

に等しくない場合は、 2 つの文字列はそれぞれ s と t で、s[i] と t[j] はそれぞれ i 番目と j 番目の文字を表し (文字の順序は 0 から始まります)、L[i, j] は s[ i ] と s[j] は、末尾の同じ部分文字列の最大長です。 L[i, j] と L[i 1,j 1] の関係を導き出すのは難しくありません。この 2 つの違いは、文字 s[i 1] と t[j 1] のペアだけであるためです。 s[i 1] と t[j 1] が異なる場合、これらで終わる部分文字列は完全に同じであることはできないため、L[i 1, j 1] は当然 0 になるはずです。 t[j 1] として、s[i] と t[j] で終わる最長の同一部分文字列の後にこれら 2 文字を追加するだけで、長さを 1 つ増やすことができます。上記 2 つの状況を組み合わせると、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 実践的なビデオ チュートリアル、ブートストラップ ビデオ チュートリアル!

以上がPHP アルゴリズム: PHP は最長共通部分文字列の問題を実装します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。