PHPにおける最長共通部分列アルゴリズムの詳細説明

PHP の最長共通部分列アルゴリズムの詳細説明

最長共通部分列 (LCS) は、主に 2 つの文字列の類似性を比較するために使用される共通文字列一致アルゴリズムです。 PHP では、動的プログラミングの考え方を通じて LCS アルゴリズムを実装することができ、アルゴリズムの原理とコード実装については以下で詳しく紹介します。

1. アルゴリズム原理
   最長共通部分列アルゴリズムの核となる考え方は、任意の 2 つの文字列 X と Y について、L が部分列 A の合計となるような最長共通部分列 L を見つけるというものです。 Y より長い共通部分列はありません。動的プログラミングの考え方に基づいて、2 次元配列 dpi を使用して、文字列 X の最初の i 文字と文​​字列 Y の最初の j 文字の最長共通部分列の長さを表すことができます。

具体的には、次の手順に従って最長の共通部分列を解決します。
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 の長さです。

2. コードの実装
   次は、PHP 言語を使用して最長共通部分列アルゴリズムを実装するコード例です。

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 配列内の各要素を計算します。最後に、バックトラッキングによって最長の共通部分列を見つけて返します。

3. 結論
   最長共通部分列アルゴリズムは、文字列の類似性問題を解決するのに適した効率的な文字列一致アルゴリズムです。動的計画法の考え方により、O(m*n) の時間計算量で最長の共通部分列を解くことができます。 PHP では、上記のコード例を使用してこのアルゴリズムを実装し、2 つの文字列の最長の共通部分シーケンスを取得できます。

以上がPHPにおける最長共通部分列アルゴリズムの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。