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）。
std::vectorbuildShiftTable(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() 的判断——少一个括号或类型错，就段错误或死循环。
