字符串匹配

int bruteForce(const std::string& t, const std::string& p) {
    int n = t.size(), m = p.size();
    for (int i = 0; i + m <= n; i++) {          // 枚举每个对齐起点
        int j = 0;
        while (j < m && t[i + j] == p[j]) j++;   // 逐字符比对
        if (j == m) return i;                    // 全部匹配
    }                                            // 失配：i++ 重来，文本指针回退到 i+1
    return -1;
}

std::vector<int> getNext(const std::string& p) {
    int m = p.size();
    std::vector<int> next(m + 1, 0);
    next[0] = next[1] = 0;
    for (int i = 1; i < m; i++) {
        int k = next[i];                    // 已知 p[0..i-1] 的最长前后缀
        while (k > 0 && p[i] != p[k]) k = next[k];
        next[i + 1] = (p[i] == p[k]) ? k + 1 : 0;
    }
    return next;
}

int kmp(const std::string& t, const std::string& p) {
    if (p.empty()) return 0;
    auto next = getNext(p);
    int n = t.size(), m = p.size(), j = 0;
    for (int i = 0; i < n; i++) {          // i 只增不减：文本指针永不回退
        while (j > 0 && t[i] != p[j]) j = next[j];  // 失配：模式跳到 next[j]
        if (t[i] == p[j]) j++;             // 匹配：模式前进
        if (j == m) return i - m + 1;      // 找到，返回起点
    }
    return -1;
}

int rabinKarp(const std::string& t, const std::string& p) {
    int n = t.size(), m = p.size();
    if (m > n) return -1;
    const long long base = 131, mod = 1000000007LL;
    long long ph = 0, th = 0, power = 1;    // power = base^(m-1) % mod
    for (int i = 0; i < m; i++) {
        ph = (ph * base + p[i]) % mod;      // 模式哈希
        th = (th * base + t[i]) % mod;      // 首窗口哈希
        if (i) power = power * base % mod;
    }
    for (int i = 0; i + m <= n; i++) {
        if (ph == th) {                     // 哈希相等 → 可能匹配
            if (t.compare(i, m, p) == 0)    // 二次校验，排除哈希碰撞
                return i;
        }
        if (i + m < n) {                    // 滚动：滑到下一窗口
            th = (th - t[i] * power % mod + mod) % mod;  // 去掉最高位
            th = (th * base + t[i + m]) % mod;           // 乘 base 加新位
        }
    }
    return -1;
}

std::vector<int> zFunction(const std::string& s) {
    int n = s.size();
    std::vector<int> z(n, 0);
    z[0] = n;
    int l = 0, r = 0;                       // 当前最右匹配段 [l, r]
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = std::min(r - i, z[i - l]);  // 复用已算信息
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;  // 暴力延伸
        if (i + z[i] > r) { l = i; r = i + z[i]; }    // 更新最右段
    }
    return z;
}
// 匹配应用：对 "P + 分隔符 + T" 求 Z，某位置 z 值 == m 即命中，等价于 KMP 的 O(n+m)。

// 28. 实现 strStr()：直接 KMP（上面的 kmp 即答案）

// 459. 重复的子字符串：s 能由某子串重复≥2次拼成？
// 结论：设 m=len，最长相等前后缀 k=next[m]，若 m%(m-k)==0 且 k>0 则可。
bool repeatedSubstring(const std::string& s) {
    int m = s.size();
    auto next = getNext(s);
    int k = next[m];                       // 整串的最长相等前后缀长度
    return k > 0 && m % (m - k) == 0;      // (m-k) 是最小循环节长度
}

// 214. 最短回文串：只在 s 前面加字符使其成回文。
// 找 s 的"最长回文前缀"，剩余部分反转补到前面。
// 技巧：构造 str = s + '#' + reverse(s)，求整体 next[len]，
//       其值即最长回文前缀长度（KMP 求最长相等前后缀）。
std::string shortestPalindrome(const std::string& s) {
    std::string rev(s.rbegin(), s.rend());
    std::string comb = s + '#' + rev;
    auto next = getNext(comb);
    int longestPrefix = next[comb.size()]; // s 的最长回文前缀长度
    std::string add(s.begin() + longestPrefix, s.end());
    std::reverse(add.begin(), add.end());
    return add + s;
}