最長公共子串問題：

給定兩個字符串，求出它們之間最長的相同子字符串的長度。

暴力解法思路：

1.以兩個字符串的每個字符為開頭，往后比較，這樣就會需要兩層循環(huán)

2.兩層循環(huán)內(nèi)部的比較方式，也是一層循環(huán)，以當(dāng)前字符為起點(diǎn)，往后遍歷比較，直到有不同就跳出這次循環(huán)，記錄下相同子字符串的長度

3.以最長的那次長度為準(zhǔn)，因此也就是有三層循環(huán)。時間復(fù)雜度O(n^3)

longest=0for 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 longest=longest length ? length:longest

動態(tài)規(guī)劃法：

1.上面的比較過程中，以i和j為起點(diǎn)開始，如果遇到不同的停止后，下一次的開始位置會進(jìn)行重復(fù)比較

2.動態(tài)規(guī)劃法-空間換時間，矩陣圖，可以把復(fù)雜度降至O(n^2)

3.str1是橫軸，str2是縱軸，table[i][j]就是以這兩個字符為結(jié)尾的最長子串的長度

4.table[0][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

假設(shè)兩個字符串分別為s和t，s[i]和t[j]分別表示其第i和第j個字符(字符順序從0開始)，再令L[i, j]表示以s[i]和s[j]為結(jié)尾的相同子串的最大長度。應(yīng)該不難遞推出L[i, j]和L[i+1,j+1]之間的關(guān)系，因為兩者其實只差s[i+1]和t[j+1]這一對字符。若s[i+1]和t[j+1]不同，那么L[i+1, j+1]自然應(yīng)該是0，因為任何以它們?yōu)榻Y(jié)尾的子串都不可能完全相同；而如果s[i+1]和t[j+1]相同，那么就只要在以s[i]和t[j]結(jié)尾的最長相同子串之后分別添上這兩個字符即可，這樣就可以讓長度增加一位。合并上述兩種情況，也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)這樣的關(guān)系。

代碼實例：

 ?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;//矩陣動態(tài)規(guī)劃法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);

以上就是本篇的全部內(nèi)容，更多相關(guān)教程請訪問php編程從入門到精通全套視頻教程，php實戰(zhàn)視頻教程，bootstrap視頻教程！

以上就是PHP算法之PHP實現(xiàn)最長公共子串的問題的詳細(xì)內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。