c++中如何实现字符串的快速匹配算法_c++ Sunday算法实现步骤【详解】

Sunday算法更快因失配时依主串模式串后字符查表跳转，非仅移1位；shift表对字符c取其在pattern最右位置i，则shift[c]=len−1−i，否则为len+1，ASCII下用vector(256,len+1)实现。

为什么 Sunday 算法比朴素匹配快？

因为 Sunday 算法在失配时，不是只右移 1 位，而是根据主串中「模式串右侧下一个字符」的值，查预计算的偏移表，一次性跳过若干位置。平均时间复杂度是 O(n)（n 是主串长度），最坏也是 O(nm)，但实际远优于朴素算法，尤其当字符集不大、模式串较短时。

关键点在于：跳得够狠，且跳得有依据——不看模式串本身失配位置，而看主串里“模式串屁股后面那个字符”是否在模式串里出现过。

如何构建 Sunday 的 shift 表？

shift 表本质是一个字符到「右移步数」的映射。对每个字符 c，定义：

• 如果 c 在模式串 pattern 中最后一次出现在索引 i（从 0 开始），则 shift[c] = pattern.Length() - 1 - i；
• 如果 c 不在 pattern 中，则 shift[c] = pattern.length() + 1（直接跳过整个模式串+1）。

注意：必须覆盖所有可能出现在主串中的字符，但实际中常只处理 ASCII（0–127）或扩展 ASCII（0–255）。用 std::vector 或 std::Array 最方便，初始化为默认偏移（即 pattern.size() + 1）。

立即学习“C++免费学习笔记（深入）”；

std::vector buildShiftTable(const std::string& pattern) {     std::vector shift(256, pattern.size() + 1);     for (int i = 0; i < pattern.size(); ++i) {         shift[static_cast(pattern[i])] = pattern.size() - i;     }     return shift; }

Sunday 主循环怎么写才不出错？

核心是维护主串起始比对位置 i，每次比较从 i 开始的 pattern.size() 个字符；失配时，取 text[i + pattern.size()]（即模式串右侧第一个字符），查 shift 表决定下一次 i 的增量。

容易踩的坑：

• i + pattern.size() 可能越界——必须保证 i 才进入比对；
• 查表前必须把字符转成 unsigned char，否则负值索引会崩；
• 偏移量加的是 shift[...]，不是减，且要确保 i 不回退（Sunday 不回溯）。

int sundaySearch(const std::string& text, const std::string& pattern) {     if (pattern.empty()) return 0;     if (pattern.size() > text.size()) return -1; 
auto shift = buildShiftTable(pattern); int i = 0; while (i <= static_cast(text.size()) - static_cast(pattern.size())) {     bool matched = true;     for (int j = 0; j < pattern.size(); ++j) {         if (text[i + j] != pattern[j]) {             matched = false;             break;         }     }     if (matched) return i;      // 失配：看 text[i + pattern.size()] 对应的 shift 值     if (i + pattern.size() < text.size()) {         unsigned char c = text[i + pattern.size()];         i += shift[c];     } else {         break;     } } return -1;
}
和 KMP、BM 比，Sunday 适合什么场景？
Sunday 实现简单、常数小、缓存友好，特别适合：

模式串较短（字节）且重复搜索不多的场景；
嵌入式或教学用途——代码不到 30 行，逻辑清晰；
主串为内存连续字符串（如 std::string），无随机访问瓶颈。

不适合：

超长模式串（> 1KB），此时 shift 表空间开销大，且 BM 的后缀预处理更高效；
需要找全部匹配位置（而不仅是首个），需微调循环但易漏边界；
Unicode 字符串（UTF-8）——不能直接用 char 查表，得先解码或改用 std::unordered_map，性能打折。

真正要注意的，是 buildShiftTable 中对字符类型的强制转换和主循环里那个 i + pattern.size()  的判断——少一个括号或类型错，就段错误或死循环。