本篇文章帶給大家的內容是PHP演算法之PHP實作最長公共子字串的問題。有一定的參考價值,有需要的朋友可以參考一下,希望對你們有幫助。
最長公用子字串問題:
給定兩個字串,求它們之間最長的相同子字串的長度。
暴力解法思維:
1.以兩個字串的每個字元為開頭,往後比較,這樣就會需要兩層循環
2.兩層循環內部的比較方式,也是一層循環,以當前字元為起點,往後遍歷比較,直到有不同就跳出這次循環,記錄下相同子字串的長度
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]就是以這兩個字元為結尾的最長子字串的長度
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
假設兩個字串分別為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中文網其他相關文章!