这是一个字符串匹配问题，但匹配规则并非直接的字符相等，而是要求两个字符串的“字符关系结构”相同。我直接用一道例题来解释这个概念和解决方法。

✨ 核心概念

两个字符串“实际上相同”意味着：它们每个位置上的字符，与其前面相同字符的出现位置关系必须完全一致。

🧩 关键思路：编码与哈希

我们可以为字符串定义一个特征编码 (Pattern Encoding)，如果两个字符串的编码相同，它们就“实际上相同”。

编码方法： 对于字符串中每个位置 i 的字符：

• 如果这个字符在字符串中是第一次出现，我们记录一个特殊值（例如 i+1 或 0）。
• 如果这个字符之前出现过，我们记录 i - last_occurrence[current_char]，即当前位置与该字符上一次出现位置的距离。

匹配过程：

1. 预处理模式串P：计算其完整的特征编码，并生成一个哈希值 (Hash Value)。
2. 滑动窗口匹配：在文本串 T 上滑动长度为 M 的窗口。
   • 计算当前窗口的特征编码哈希值。
   • 与模式串 P 的哈希值比较，相同则计数加一。

🚀 算法步骤

1. 初始化：创建一个数组 last_occurrence[26] 记录每个字符在当前窗口最后一次出现的位置，初始化为 -1。
2. 计算P的哈希：对模式串 P 进行编码并计算哈希值 hashP。
3. 滑动窗口：
   • 对于 T 的每个起始位置 i (0 ≤ i ≤ N-M)：
     • 更新当前窗口的 last_occurrence 信息。
     • 计算当前窗口的编码哈希 currentHash。
     • 若 currentHash == hashP，则找到一个匹配子串。
4. 返回：匹配子串的总数。

💻 代码框架（C++）

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

int findP(char T[], char P[], int N, int M) {
    // 1. 计算模式串P的编码哈希
    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++) {
        // 计算窗口 T[i...i+M-1] 的pattern哈希
        long long currentHash = computeWindowHash(T, i, M, last);
        
        if (currentHash == hashP) {
            count++;
        }
    }
    
    return count;
}

💎 复杂度分析

• 时间复杂度：O(N)。滑动窗口处理文本串 T 一次，使用滚动哈希时每个窗口的哈希计算是 O(1) 的。
• 空间复杂度：O(1)。主要使用了一个固定大小的 last_occurrence 数组（字符集大小固定）。

这种方法的巧妙之处在于将复杂的字符关系约束转化为可计算的数值，从而利用高效的哈希技术进行快速匹配。