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

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

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

为什么 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::vector<int> buildShiftTable(const std::string& pattern) {
    std::vector<int> shift(256, pattern.size() + 1);
    for (int i = 0; i (pattern[i])] = pattern.size() - i;
    }
    return shift;
}</int></int>

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

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

容易踩的坑：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

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;
<pre class="brush:php;toolbar:false;">auto shift = buildShiftTable(pattern);
int i = 0;
while (i (text.size()) - static_cast<int>(pattern.size())) {
    bool matched = true;
    for (int j = 0; j <p>}</p></int>