PHP 求解两字符串所有公共子序列及最长公共子序列 支持多字节字符串

function public_sequence(string $str1, string $str2): array{    $data = [[-1, -1, '', 0, '']]; // 子序列容器【横坐标 纵坐标 当前子序列 长度 足迹】    $arr  = []; // 动态规划容器    $arr1 = mb_str_split($str1);    $arr2 = mb_str_split($str2);    $len1 = count($arr1);    $len2 = count($arr2);    // 动态规划    for ($y = 0; $y < $len2; ++$y) {        for ($x = 0; $x < $len1; ++$x) {            $arr[$y][$x] = $arr1[$x] === $arr2[$y] ? 1 : 0;            e($arr[$y][$x], 'n'); // 打印数据        }        e(); // 换行    }    // 寻找所有子序列    $len = $len1 > $len2 ? $len1 : $len2;    for ($i = 0; $i < $len; ++$i) {        foreach ($data as &$value) {            ++$value[0]; // 横坐标            ++$value[1]; // 纵坐标            $len = $value[3] + 1; // 长度            // 纵坐标固定，横坐标增加，检验横行数据            for ($x = $value[0]; $x < $len1; ++$x) {                if ($value[1] >= $len2) break;                if ($arr[$value[1]][$x] === 1)                     $data[] = [$x, $value[1], $value[2] . $arr1[$x], $len, $value[4] . '(' . $x . ',' . $value[1] . ')'];            }            // 横坐标固定，纵坐标增加，检验纵行数据            for ($y = $value[1] + 1; $y < $len2; ++$y) {                if ($value[0] >= $len1) break;                if ($arr[$y][$value[0]] === 1)                     $data[] = [$value[0], $y, $value[2] . $arr2[$y], $len, $value[4] . '(' . $value[0] . ',' . $y . ')'];            }        }    }    return $data;}function long_public_sequence(string $str1, string $str2): array{    $data = []; // 最长子序列容器    $tmp  = []; // 临时子序列容器    $len = 0; // 最长子序列长度    // 获取所有公共子序列    $subsequence = public_sequence($str1, $str2);    // 找到最长子序列长度及个数    foreach ($subsequence as $value) {        if ($len > $value[3]) continue;        $len = $value[3];        $tmp[] = $value;    }    // 根据最长子序列长度筛选数据    foreach ($tmp as $value) {        if ($len === $value[3]) $data[] = $value;    }    return $data;}$str1 = '安保处的';$str2 = '安保的';v(public_sequence($str1, $str2));vd(long_public_sequence($str1, $str2));

执行结果：

来源地址：https://blog.csdn.net/m0_37711659/article/details/132234726