PHP — LCS
in PHP with 0 comment, Views is 29

PHP — LCS

in PHP with 0 comment, Views is 29

问题描述

给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)

str1:advantagestr2:didactical

则这两个字符串的最长公共子序列长度为 4,最长公共子序列是:data

代码实现

该算法详解请看:《C语言数据结构(一)绪论(6)动态规划(2)》

<?php
/**
 * 生成 LCS 迭代路径图和打印路径图
 * @param string $str1 字符串1
 * @param string $str2 字符串2
 * @param array  $map  迭代路径图
 * @param array  $path 打印路径图
 */
function lcs_map(string $str1, string $str2, array &$map, array &$path)
{
    for ($i = 0; $i <= strlen($str1); $i++) {

        for ($j = 0; $j <= strlen($str2); $j++) {

            $path[$i][$j] = 0; // 初始化 path

            if (0 == $i || 0 == $j) {

                // map 初始行和初始列均为 0
                $map[$i][$j] = 0;

            } else if ($str1[$i - 1] == $str2[$j - 1]) {

                // 字符相同,则左上角+1
                $map[$i][$j] = $path[$i][$j] = $map[$i - 1][$j - 1] + 1;

            } else {

                // 字符不相同,则选择上和左中最大值
                $map[$i][$j] = ($map[$i - 1][$j] > $map[$i][$j - 1]) ?
                                $map[$i - 1][$j] : $map[$i][$j - 1];

            }

        }

    }
}

/**
 * 返回最长公共子序列
 * @param string $str1 字符串1
 * @param string $str2 字符串2
 * @param array  $path 打印路径
 * @param int    $max  最长路径长度
 * @return string 子序列字符串
 */
function LCS(string $str1, string $str2, array $path, int $max)
{
    $str = []; // 存储字符串

    $j = strlen($str2); // 初始化 $j

    for ($i = strlen($str1); $i > 0; $i--) {

        // 每当匹配到一个字符以后,下一个字符必然在该列之前,而非该列之后
        // 因此这里不需要每次循环都初始化 $j
        for (; $j > 0; $j--) {

            if ($path[$i][$j] == $max) {

                // 因为是从后往前遍历,所以需要前端插入
                array_unshift($str, $str1[$i - 1]); 

                $max--; // 路径长度 - 1

                break; // 改行已找到匹配字符,跳过该行

            }

        }

        if (0 == $max) break; // 路径长度为 0,退出循环

        // 这里会出现一个问题
        // 如果一行都没有匹配项,那么 $j 就会循环至 0,无法参与下一行匹配
        // 因此这里做一个判断,如果路径长度 > 0 的时候 $j 已经减小到 0
        // 那么就初始化 $j
        if (0 == $j && $max > 0) $j = strlen($str2);

    }

    return implode('', $str); // 将字符数组拼接成字符串返回
}

$str1 = 'advantage';

$str2 = 'didactical';

if ($argc > 1) {

    $str1 = $argv[1];

    $str2 = $argv[2];

}

$map  = []; // 存储 LCS 迭代路径
$path = []; // 存储打印路径
  
lcs_map($str1, $str2, $map, $path);

echo "\nLCS 迭代路径图 MAP:\n";

for ($i = 0; $i <= strlen($str1); $i++) {

    for ($j = 0; $j <= strlen($str2); $j++) {
        
        echo $map[$i][$j] . "\t";

    }

    echo "\n";

}

echo "\nLCS 打印路径图 Path:\n";

for ($i = 0; $i <= strlen($str1); $i++) {

    for ($j = 0; $j <= strlen($str2); $j++) {
        
        echo $path[$i][$j] . "\t";

    }

    echo "\n";

}

echo "\n最长公共子序列:" .
     LCS($str1, $str2, $path, $map[strlen($str1)][strlen($str2)]) .
     "\n\n";

1.png

2.png

Responses
选择表情