如何在Excel中高效检测两字符串间N长度及以上公共子串

嗨，你遇到的这个问题我之前也碰到过——暴力遍历的方式在字符串稍长时就会因为重复调用InStr（每次都是O(M)的时间复杂度，M是str2的长度）导致效率急剧下降，尤其是当str1和str2都有上千字符的时候，数千次的重复计算确实很头疼。咱们换个思路，从预处理str2入手，能大幅提升效率。

核心优化思路：用哈希集合预处理str2的所有有效子串 #

暴力法的痛点在于每次检查str1的子串时，都要在str2里从头找一遍。如果我们先把str2中所有长度≥N的子串都存到一个哈希集合（比如VBA里的Scripting.Dictionary）里，之后检查str1的子串时就能做到O(1)的快速查找，整体效率会提升很多。

具体实现步骤（VBA示例） #

1. 预处理str2，生成所有长度≥N的子串集合

首先遍历str2的所有起始位置，把每个位置开始、长度从N到剩余长度的子串都存入字典（自动去重，避免重复存储相同子串）：

Sub OptimizedSubstringCheck()
    Dim str1 As String, str2 As String
    Dim minSubLen As Integer
    Dim subStrCache As Object
    Dim startPos As Integer, subLen As Integer
    Dim currentSub As String
    
    ' 初始化你的字符串和最小长度N
    str1 = "AKMDHVIIDMEHGOKDJNFJD"
    str2 = "DJRWFNCGNDKDJHBC"
    minSubLen = 4
    
    ' 创建字典作为哈希集合，存储str2的所有有效子串
    Set subStrCache = CreateObject("Scripting.Dictionary")
    
    ' 遍历str2的所有起始位置
    For startPos = 1 To Len(str2)
        ' 子串长度从minSubLen开始，直到当前起始位置到str2末尾的最大长度
        For subLen = minSubLen To Len(str2) - startPos + 1
            currentSub = Mid(str2, startPos, subLen)
            ' 只存不重复的子串
            If Not subStrCache.Exists(currentSub) Then
                subStrCache.Add currentSub, True
            End If
        Next subLen
    Next startPos

2. 遍历str1的有效子串，快速查询

现在检查str1中所有长度≥N的子串时，直接去字典里查就行——注意：str1中长度超过str2的子串肯定不可能存在于str2中，所以我们可以把检查的最大长度限制为Len(str2)，减少不必要的循环：

Dim isFound As Boolean
    isFound = False
    Dim maxCheckLen As Integer
    maxCheckLen = Len(str2) ' 超过str2长度的子串无需检查
    
    For startPos = 1 To Len(str1)
        ' 子串长度取minSubLen到「剩余长度」和「maxCheckLen」的较小值
        For subLen = minSubLen To Application.WorksheetFunction.Min(maxCheckLen, Len(str1) - startPos + 1)
            currentSub = Mid(str1, startPos, subLen)
            If subStrCache.Exists(currentSub) Then
                Debug.Print "找到匹配子串：" & currentSub
                isFound = True
                ' 如果只需要判断是否存在，这里可以直接跳出所有循环
                ' GoTo ExitCheck
            End If
        Next subLen
    Next startPos

ExitCheck:
    If Not isFound Then
        Debug.Print "未找到任何符合条件的子串"
    End If
    
    ' 清理对象
    Set subStrCache = Nothing
End Sub

进阶优化：滚动哈希（Rabin-Karp算法） #

如果你的字符串特别长（比如百万级字符），上面的方法可能会因为存储大量子串占用过多内存。这时候可以用滚动哈希来优化：只存储子串的哈希值，而不是子串本身，大幅减少内存占用，同时保持O(1)的查询效率。

简单来说，就是给每个子串计算一个唯一的哈希值（通过预计算前缀哈希和幂次，快速得到任意子串的哈希），然后把str2的有效子串哈希存入集合，再计算str1的子串哈希去匹配。需要注意的是，要选择合适的基数和模数来降低哈希碰撞的概率，也可以用双哈希（两个不同的哈希规则）进一步避免碰撞。

效率对比 #

• 暴力法的时间复杂度是O(L1*(L2-N+1)*(L2))，其中L1是str1长度，L2是str2长度
• 优化后的哈希集合方法时间复杂度是O(L2*(L2-N+1) + L1*(min(L1, L2)-N+1))，由于查询是O(1)，实际运行速度会比暴力法快几个数量级，尤其是当L1和L2都较大时。

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