如何高效查找字符串A中任意8字节子串是否存在于字符串B中？

我们有两个MB级长度的字符串$strA和$strB，需要判断$strA中是否存在任意一个8字节子串出现在$strB中。当前实现的方法可行但速度极慢，代码如下：

function FindAnySubstring($strA,$strB)
{
    for( $i=0; $i<strlen($strA)-8; $i++ )
    {
        $toFind=subStr($strA,$i,8);
        $pos=strpos($strB,$toFind);
        if( $pos === FALSE )
            continue;
        return [$i,$pos];
    }
    return FALSE;
}

示例数据 #

为便于演示，使用较短的样本：

$strA = 'abcdefghijKLMNOPQRstuvxyz';
$strB = 'ldsf32vKLMNOPQR4fa156232543';

预期结果 #

[11,8]（对应$strA的第11位和$strB的第8位）

当前执行耗时 #

当$strA和$strB长度为3,321,792字节时，找到结果的耗时在0到2530秒之间（取决于子串位置），期望能提升两个数量级的效率。

已考虑的思路 #

• 先查找更短的子串，找到后再验证剩余部分；测试后无性能提升
• 使用并行处理；虽有效但实现难度较高

优化方案：哈希预存法 #

原方法的核心问题是时间复杂度为O(M*N)（M是$strA长度，N是$strB长度），每次遍历$strA的子串都要在$strB中做全量查找，这对MB级字符串来说效率极低。

优化思路是先预处理$strB，把所有8字节子串存入哈希表（关联数组），后续遍历$strA时直接查表，整体时间复杂度降到O(M+N)，性能会有数量级的提升。

实现代码1：直接存储子串 #

function FindAnySubstringOptimized($strA, $strB) {
    $lenB = strlen($strB);
    if ($lenB < 8) return false;
    
    // 预存$strB中所有8字节子串及其起始位置
    $bSubstrings = [];
    for ($j = 0; $j <= $lenB - 8; $j++) {
        $sub = substr($strB, $j, 8);
        if (!isset($bSubstrings[$sub])) {
            $bSubstrings[$sub] = $j; // 只存第一个出现的位置
        }
    }
    
    $lenA = strlen($strA);
    if ($lenA < 8) return false;
    
    // 遍历$strA的8字节子串，查询哈希表
    for ($i = 0; $i <= $lenA - 8; $i++) {
        $subA = substr($strA, $i, 8);
        if (isset($bSubstrings[$subA])) {
            return [$i, $bSubstrings[$subA]];
        }
    }
    
    return false;
}

实现代码2：哈希值优化内存 #

如果$strB长度极大，存储所有8字节子串会占用较多内存，可以改用哈希值（如crc32）代替完整子串，减少内存占用。同时为避免哈希碰撞，查到匹配后需要验证原字符串：

function FindAnySubstringOptimizedWithHash($strA, $strB) {
    $lenB = strlen($strB);
    if ($lenB < 8) return false;
    
    $bHashes = [];
    for ($j = 0; $j <= $lenB - 8; $j++) {
        $hash = crc32(substr($strB, $j, 8));
        if (!isset($bHashes[$hash])) {
            $bHashes[$hash] = $j;
        }
    }
    
    $lenA = strlen($strA);
    if ($lenA < 8) return false;
    
    for ($i = 0; $i <= $lenA - 8; $i++) {
        $hash = crc32(substr($strA, $i, 8));
        if (isset($bHashes[$hash])) {
            // 验证原字符串，避免哈希碰撞
            $subA = substr($strA, $i, 8);
            $subB = substr($strB, $bHashes[$hash], 8);
            if ($subA === $subB) {
                return [$i, $bHashes[$hash]];
            }
        }
    }
    
    return false;
}

额外小优化 #

原代码中for循环每次调用strlen($strA)会重复计算字符串长度，提前把长度存入变量能小幅提升性能，上述优化方案已包含这一点。

内容的提问来源于stack exchange，提问作者Gajowy