当前位置：首页 > news >正文

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

news 2025/8/15 1:14:54


/*** 获取两字符串所有公共子序列【不连续的】 例：abc ac => ac** @param string $str1 字符串1* @param string $str2 字符串2** @return array*/
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;
}/*** 获取两字符串所有最长公共子序列 注意：最长字符串子序列可能有多个** @param string $str1 字符串1* @param string $str2 字符串2** @return array*/
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));

执行结果：