字符串模式匹配：统计A中与B模式等价的子串数量

嘿，这个问题挺典型的，而且针对1e7长度的字符串，必须得找个线性时间的高效解法才行！你之前尝试的模式转换思路方向是对的，但直接对每个子串做转换会导致O(n*m)的时间复杂度，根本扛不住大字符串，这里给你一个更巧妙的思路：

核心思路：把模式等价转化为差分序列匹配 #

首先我们要明确：两个长度相同的字符串模式等价（即其中一个是另一个的排列的模式），本质上是它们的「字符相等关系序列」完全一致。比如：

• "xx"的相等关系是「第二个字符等于第一个」，对应差分标记为[1]
• "aa"的相等关系也是「第二个字符等于第一个」，差分标记同样是[1]
• "xy"的相等关系是「第二个字符不等于第一个」，差分标记是[0]，"yx"的差分标记也是[0]，所以它们模式等价

换句话说，两个字符串模式等价，当且仅当它们的差分序列完全相同。这里的差分序列是指：对字符串中每个位置i（从1开始），标记当前字符与前一个字符是否相等（相等为1，不等为0），得到的长度为m-1的序列（m是原字符串长度）。

基于这个结论，问题就转化为经典的字符串匹配问题：

1. 把B转换成它的差分序列（长度为m-1）
2. 把A转换成它的差分序列（长度为n-1）
3. 统计B的差分序列在A的差分序列中出现的次数——这个次数就是你要的答案！

具体步骤&实现 #

1. 边界情况处理

• 如果B的长度是1：A中所有长度为1的子串都符合条件，直接返回A的长度
• 如果A的长度小于B的长度：返回0

2. 生成差分序列

比如对B="xx"，生成的差分序列是[1]；对A="aabbccd"，生成的差分序列是[1,0,1,0,1,0]。

3. 用KMP算法做线性匹配

KMP算法可以在O(n+m)的时间内完成匹配，完全适配1e7长度的字符串。而且我们甚至不需要提前存储A的整个差分序列——可以在匹配过程中动态计算当前位置的差分标记，节省内存。

给你一段C++风格的核心代码示例（适配大字符串场景）：

#include <vector>
#include <string>
using namespace std;

int countMatchingSubstrings(const string& A, const string& B) {
    int n = A.size();
    int m = B.size();
    if (m == 1) return n;
    if (n < m) return 0;

    // 生成B的差分序列pattern
    vector<int> pattern;
    pattern.reserve(m-1);
    for (int i = 1; i < m; ++i) {
        pattern.push_back(B[i] == B[i-1] ? 1 : 0);
    }

    // 计算KMP前缀函数
    int pattern_len = pattern.size();
    vector<int> prefix(pattern_len, 0);
    for (int i = 1; i < pattern_len; ++i) {
        int j = prefix[i-1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefix[j-1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        prefix[i] = j;
    }

    // 动态计算A的差分并匹配
    int count = 0;
    int j = 0;
    for (int i = 1; i < n; ++i) {
        int current = (A[i] == A[i-1]) ? 1 : 0;
        // KMP匹配逻辑
        while (j > 0 && current != pattern[j]) {
            j = prefix[j-1];
        }
        if (current == pattern[j]) {
            j++;
        }
        // 匹配成功一次
        if (j == pattern_len) {
            count++;
            j = prefix[j-1];
        }
    }
    return count;
}

为什么这个方法高效？ #

• 时间复杂度：O(n+m)，不管A的长度是1e7还是更大，都能线性处理
• 空间复杂度：O(m)，只需要存储B的差分序列和KMP的前缀数组，内存占用极小
• 完全避免了暴力遍历每个子串的高复杂度问题，完美解决你的痛点

替代方案：滚动哈希 #

如果内存非常紧张（比如连O(m)的空间都不想用），可以用滚动哈希的方式计算差分序列的哈希值，滑动窗口比较哈希值是否相等。这种方法空间复杂度是O(1)，但要注意选择合适的哈希基数和模数，或者用双哈希来避免冲突。

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