ホームページ >バックエンド開発 >PHPチュートリアル >PHPにおける最長共通部分列アルゴリズムの詳細説明
PHP の最長共通部分列アルゴリズムの詳細説明
最長共通部分列 (LCS) は、主に 2 つの文字列の類似性を比較するために使用される共通文字列一致アルゴリズムです。 PHP では、動的プログラミングの考え方を通じて LCS アルゴリズムを実装することができ、アルゴリズムの原理とコード実装については以下で詳しく紹介します。
具体的には、次の手順に従って最長の共通部分列を解決します。
1) dp 配列を初期化します。ここで、dpi は文字列の最初の i 文字を表します。 Y の最初の j 文字の共通部分列。
2) 文字列 X と Y の各文字をトラバースします。X[i] が Y[j] と等しい場合、dpi の値は dpi-1 1 で取得できます。それ以外の場合、dpi の値は dpi- 1 および dpi 単位の大きい値。
3) 最後に、dpm は文字列 X と Y の最長共通部分列の長さです。ここで、m と n は文字列 X と Y の長さです。
function LCS($str1, $str2) { $m = strlen($str1); $n = strlen($str2); $dp = array(); for ($i = 0; $i <= $m; $i++) { $dp[$i][0] = 0; } for ($j = 0; $j <= $n; $j++) { $dp[0][$j] = 0; } for ($i = 1; $i <= $m; $i++) { for ($j = 1; $j <= $n; $j++) { if ($str1[$i - 1] == $str2[$j - 1]) { $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1; } else { $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]); } } } $lcs = ''; $i = $m; $j = $n; while ($i > 0 && $j > 0) { if ($str1[$i - 1] == $str2[$j - 1]) { $lcs = $str1[$i - 1] . $lcs; $i--; $j--; } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) { $i--; } else { $j--; } } return $lcs; } $str1 = "abcdefg"; $str2 = "bcedgh"; $lcs = LCS($str1, $str2); echo "最长公共子序列: " . $lcs;
上記のコードでは、まず、バイナリ次元配列 dp を初期化し、最初の行と最初の列の要素を 0 に設定します。次に、ネストされた 2 つの for ループを使用して、dp 配列内の各要素を計算します。最後に、バックトラッキングによって最長の共通部分列を見つけて返します。
以上がPHPにおける最長共通部分列アルゴリズムの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。