核心思路

两个字符串"实际上相同" ⇔ 它们每个位置的字符与前面相同字符的距离模式完全一致。

关键观察

对于字符串中每个位置 i，定义：

pattern[i] = i - last_occurrence[current_char]

如果该字符是第一次出现，则 pattern[i] = i + 1（或一个特殊值）

算法步骤

1. 预处理模式串P：

   • 计算P的pattern编码
   • 计算该编码的哈希值

2. 滑动窗口匹配：

   • 维护文本T中当前窗口内每个字符的最后出现位置
   • 对每个起始位置，计算当前窗口的pattern编码哈希值
   • 与P的哈希值比较，相同则计数+1

3. 滚动更新：

   • 窗口滑动时，只更新进入和离开的字符信息
   • 使用哈希可在O(1)时间内比较

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(字符集大小)

代码框架

int findP(char T[], char P[], int N, int M) {
    // 1. 计算P的pattern编码哈希
    long long hashP = computePatternHash(P, M);
    
    int count = 0;
    int last[26]; // 记录每个字符最后出现位置
    memset(last, -1, sizeof(last));
    
    // 2. 滑动窗口匹配
    for (int i = 0; i <= N - M; i++) {
        if (i == 0) {
            // 计算第一个窗口的pattern
        } else {
            // 滚动更新窗口pattern
        }
        
        // 比较当前窗口与P的pattern哈希
        if (currentHash == hashP) {
            count++;
        }
    }
    
    return count;
}

举例说明

P = "pqp"的pattern编码：

• p: 1 (第一次出现)
• q: 2 (第一次出现)
• p: 2 (距离上一个p的位置差=2)

T中任何具有相同距离模式的子串都是匹配的。