Sunday算法实际更快因其跳步更激进：匹配失败时查看主串中对齐模式串末尾后一位的字符，依其在模式串最右位置决定跳距，平均跳过更多字符。
为什么Sunday算法比KMP在实际场景中更快
Sunday算法不是理论最优，但平均性能常优于KMP和BM——因为它跳得更“大胆”。核心在于：每次匹配失败时，看主串中**对齐到模式串末尾后一位的字符**（即text[i + m]），查它在模式串中最后一次出现的位置，直接跳过中间所有可能。这个“看后面一位”的策略，让多数情况下跳长距离，尤其适合英文文本、日志等局部重复少的场景。
关键点：text[i + m]可能越界（比如已到末尾），此时直接结束；跳距 = m - last_occurrence[text[i + m]]，若该字符不在模式串中，则跳 m + 1 步。
如何构建last_occurrence表（含边界处理）
这个表本质是字符→最右下标的映射，但必须覆盖所有可能遇到的字符（不能只建ASCII 0–127）。常见错误是用std::map<char int></char>或固定大小数组却忽略负char或扩展ASCII。
- 推荐用
std::vector<int></int>，大小设为256，初始化为-1（表示未出现） - 遍历模式串
pattern时，对每个pattern[j]执行last_occurrence[static_cast<unsigned char>(pattern[j])] = j</unsigned>——强制转unsigned char避免负索引 - 不要漏掉空字符串判断：若
pattern.empty()，直接返回0或按需处理
完整可跑的Sunday查找函数（带越界防护）
下面这段代码处理了所有边界：主串为空、模式串为空、主串长度不足、跳步后越界。返回第一个匹配起始下标，没找到返回-1。
立即学习“C++免费学习笔记（深入）”；
int sunday_search(const std::string& text, const std::string& pattern) {
if (pattern.empty()) return 0;
if (text.empty() || text.size() < pattern.size()) return -1;
<pre class="brush:php;toolbar:false;">std::vector<int> last_occurrence(256, -1);
for (size_t j = 0; j < pattern.size(); ++j) {
unsigned char c = static_cast<unsigned char>(pattern[j]);
last_occurrence[c] = static_cast<int>(j);
}
size_t i = 0;
while (i <= text.size() - pattern.size()) {
// 检查当前对齐位置是否匹配
bool matched = true;
for (size_t j = 0; j < pattern.size(); ++j) {
if (text[i + j] != pattern[j]) {
matched = false;
break;
}
}
if (matched) return static_cast<int>(i);
// 计算跳步：看 text[i + m] 处的字符
size_t next_pos = i + pattern.size();
if (next_pos >= text.size()) break; // 越界，无法再跳
unsigned char c = static_cast<unsigned char>(text[next_pos]);
int shift = pattern.size() - last_occurrence[c];
i += (shift > 0 ? shift : 1); // 至少挪1位，防死循环
}
return -1;}
什么时候不该用Sunday算法
它快是有条件的。如果模式串极长（比如>1KB）、或主串是高度重复数据（如DNA序列、二进制dump），Sunday的跳步优势会减弱，而KMP的确定性O(n+m)反而更稳。
- 模式串含大量重复字符（如"aaaaab"）时，
last_occurrence表里很多位置被覆盖，跳距变小，退化成暴力扫描 - 需要找全部匹配位置？Sunday单次跳过可能漏掉重叠匹配（如在"aaaa"中找"aa"，它默认不重叠），得手动控制i只+1
- 嵌入式环境内存紧张？256字节的
last_occurrence表虽小，但若同时跑多个不同pattern的查找，别忘了复用或清零
真正要注意的是：跳步逻辑里那个i += (shift > 0 ? shift : 1)——很多人写成i += shift，当shift == 0（比如pattern末尾字符在自己内部多次出现）就会卡死。这个兜底+1，是实操中最容易漏掉的一行。
