PHP アルゴリズム設計のアイデア: 最大共通部分列問題に対する効率的な解決策を達成するにはどうすればよいですか?
最長共通部分列 (LCS) は、2 つの文字列内の最長の同一部分列を見つける問題です。実際のアプリケーションでは、LCS はテキストの類似性比較、バージョン管理、DNA 配列比較などの分野で広く使用されています。この記事では、この問題を解決するための効率的な解決策を紹介し、具体的なコード例を示します。
アルゴリズムのアイデア:
ダイナミック プログラミングは、LCS 問題を解決する一般的な方法です。 LCS 問題には最適な部分構造特性があります。つまり、2 つのシーケンスの最長共通部分列は、部分問題の最長共通部分列によって構築できます。この特性に従って、動的計画法を使用して LCS 問題を解決できます。
具体的なアルゴリズムの手順は次のとおりです。
2 次元配列 dpm 1 を作成します。ここで、m と n はそれぞれ 2 つの入力文字列の長さです。
最初の文字列の i 番目の文字と 2 番目の文字列の j 番目の文字について、2 つの文字列の各文字をトラバースします。
コード例:
functionlongestCommonSubsequence($str1, $str2){
$m = strlen($str1); $n = strlen($str2); $dp = array(); for($i=0; $i<=$m; $i++){ $dp[$i] = array_fill(0, $n+1, 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--; } else if($dp[$i-1][$j] > $dp[$i][$j-1]){ $i--; } else{ $j--; } } return $lcs;
}
$ str1 = "ABCBDAB";
$str2 = "BDCAB";
$lcs =longestCommonSubsequence($str1, $str2);
echo "入力文字列: $str1 および $str2
" ;
echo "最長の共通部分シーケンスは次のとおりです: $lcs
";
?>
上記のコードは出力します:
入力文字列: ABCBDAB およびBDCAB
最長共通部分列は次のとおりです: BCBA
結論:
この記事では、動的プログラミング アルゴリズムを使用して最大共通部分列問題を解決するアイデアと、特定の PHP コード例を紹介します。動的計画法を使用すると、LCS 問題を効率的に解決できます。このアルゴリズムの時間計算量は O(m*n) です。ここで、m と n はそれぞれ 2 つの入力文字列の長さです。実際のアプリケーションでは、スペースの複雑さを軽減するためにローリング アレイなどの技術を使用するなど、ニーズに応じてアルゴリズムを最適化できます。
以上がPHP アルゴリズム設計のアイデア: 最大共通部分列問題に対する効率的な解決策を達成するには?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。