PHP项目怎么实现子序列匹配？

本文目录导读：

1. 方案一：双指针法（最常用，推荐）
2. 方案二：使用 strpos + 偏移量
3. 方案三：正则表达式法（不推荐用于大规模数据）
4. 进阶需求：如何找到所有子序列？
5. 总结与建议

PHP项目中实现子序列匹配,常见的方式有以下几种，我先帮你区分一下“子串”和“子序列”这两个概念，因为很多人会混淆：

• 子串：必须是原字符串中连续的一段 ("abc" in "aabcd")。
• 子序列：不要求连续，但字符的相对顺序必须保持不变 ("ac" in "abcd")。

针对子序列匹配，以下提供三种实用的PHP实现方案，从基础到进阶。

双指针法（最常用，推荐）

这是判断一个字符串是否是另一个字符串的子序列的标准方法，时间复杂度为 O(n + m)，空间复杂度为 O(1)。

function isSubsequence(string $sub, string $str): bool {
    $i = 0; // 指向 $sub
    $j = 0; // 指向 $str
    $lenSub = strlen($sub);
    $lenStr = strlen($str);
    while ($i < $lenSub && $j < $lenStr) {
        if ($sub[$i] === $str[$j]) {
            $i++; // 匹配上一个，移动子序列指针
        }
        $j++; // 无论是否匹配，主字符串指针始终后移
    }
    // $i 走到了尽头，说明 $sub 的所有字符都在 $str 中按顺序找到了
    return $i === $lenSub;
}
// 使用示例
$result1 = isSubsequence("abc", "ahbgdc"); // true
$result2 = isSubsequence("axc", "ahbgdc"); // false
echo $result1 ? 'true' : 'false'; // 输出: true

使用 strpos + 偏移量

如果字符串较短或不需要极高性能,可以用内置函数实现，代码更简洁。

function isSubsequenceByStrpos(string $sub, string $str): bool {
    $offset = 0;
    for ($i = 0; $i < strlen($sub); $i++) {
        $char = $sub[$i];
        // 从上次找到的位置之后开始查找当前字符
        $pos = strpos($str, $char, $offset);
        if ($pos === false) {
            return false; // 没找到
        }
        // 更新偏移量：必须找下一个字符，所以从 $pos + 1 开始
        $offset = $pos + 1;
    }
    return true;
}
// 使用示例
var_dump(isSubsequenceByStrpos("ace", "abcde")); // bool(true)

注意：这种方法的性能不如双指针法，因为它每次调用 strpos 都要进行一次内部搜索，但代码可读性较好。

正则表达式法（不推荐用于大规模数据）

利用正则表达式的特性,将子序列的每个字符之间用 连接。

function isSubsequenceByRegex(string $sub, string $str): bool {
    // 将 "abc" 转换为 "/^a.*b.*c.*$/"
    $pattern = '/^' . implode('.*', str_split($sub)) . '.*$/';
    return (bool) preg_match($pattern, $str);
}
// 使用示例
var_dump(isSubsequenceByRegex("abc", "ahbgdc")); // bool(true)

缺点：

1. 性能较差（需要编译正则引擎）。
2. 如果子序列中包含正则特殊字符（如 等），需要先 preg_quote 转义。

进阶需求：如何找到所有子序列？

如果需求是生成一个字符串的所有子序列（而不是判断），通常使用递归或回溯法，以下是生成所有子序列的示例：

function getAllSubsequences(string $str): array {
    $result = [];
    $length = strlen($str);
    // 回溯函数
    $backtrack = function(string $current, int $start) use ($str, $length, &$result, &$backtrack) {
        // 收集当前路径（空字符串通常被排除）
        if ($current !== '') {
            $result[] = $current;
        }
        // 从 $start 开始，尝试每个字符
        for ($i = $start; $i < $length; $i++) {
            $backtrack($current . $str[$i], $i + 1); // 取当前字符，继续向后
        }
    };
    $backtrack('', 0);
    return $result;
}
// 使用示例
$subseqs = getAllSubsequences("abc");
print_r($subseqs);
/* 输出（顺序可能不同）：
Array
(
    [0] => a
    [1] => ab
    [2] => abc
    [3] => ac
    [4] => b
    [5] => bc
    [6] => c
)
*/

总结与建议

如果你是在进行大量字符串的子序列匹配（例如一个“词库”匹配另一个“文档”），还可以考虑预处理索引表（比如记录每个字符在母串中出现的位置列表），然后用二分查找加速匹配，这种方案在LeetCode的“判断子序列”进阶题中很常见，如果项目有需要可以再深入展开。