問題: 最長共通部分列 (PHP)

最長共通部分列 (PHP)

問題

二つの文字列を入力として受け取り、動的計画法で最長共通部分列の長さを求めてください。さらに表を後ろからたどって最長共通部分列を一つ復元し、表示します。

入力例

ABCBDAB
BDCABA

出力例

長さ: 4
部分列: BCBA

参照コード

コピーはできません。自分でタイピングしてください。

<?php
$s = trim(fgets(STDIN));
$t = trim(fgets(STDIN));
$n = strlen($s);
$m = strlen($t);
$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
for ($i = 1; $i <= $n; $i++) {
    for ($j = 1; $j <= $m; $j++) {
        if ($s[$i - 1] == $t[$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 = $n;
$j = $m;
while ($i > 0 && $j > 0) {
    if ($s[$i - 1] == $t[$j - 1]) {
        $lcs = $s[$i - 1] . $lcs;
        $i--;
        $j--;
    } elseif ($dp[$i - 1][$j] >= $dp[$i][$j - 1]) {
        $i--;
    } else {
        $j--;
    }
}
echo "長さ: " . $dp[$n][$m] . "\n";
echo "部分列: " . $lcs . "\n";
?>

最長共通部分列 (PHP)

問題

入力例

出力例

参照コード

入力エリア