9 字符串

9.1 字符串哈希

constexpr int MOD = 1610612741;  // 212370440130137957LL 这个数虽大但是乘法会溢出
constexpr int base = 131;

// 单哈希法获得一个字符串的哈希值
ull getHash(string &s) {
    ull res = 0;
    for (int i = 0; i < s.length(); i++) {
        res = (base * res + (ull)s[i]) % MOD;
    }
    return res;
}

9.2 区间回文查询

依靠字符串哈希值的前缀和与后缀和

using ull = unsigned long long;
constexpr int MAXN = 2E5 + 5;
constexpr ull MOD = 1610612741;
constexpr ull base = 131;
class MyStr {
   private:
    int n;
    char s[MAXN];
    ull pre[MAXN], suf[MAXN];
    void init() {
        pwb[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            pwb[i] = pwb[i - 1] * base % MOD;
        }
    }
    ull hashL(int l, int r) { return (pre[r] - pre[l - 1] * pwb[r - l + 1] % MOD + MOD) % MOD; }
    ull hashR(int l, int r) { return (suf[l] - suf[r + 1] * pwb[r - l + 1] % MOD + MOD) % MOD; }

   public:
    ull pwb[MAXN];  // power of base : pwb[i]即base的i次幂
    MyStr() { init(); }
    // 建立哈希，每次读入新的字符串就要调用一下以更新哈希值
    void build(int n, char str[]) {
        pre[0] = suf[n + 1] = 0;
        for (int i = 1; i <= n; i++) {
            int j = n - i + 1;
            pre[i] = (pre[i - 1] * base + (ull)str[i]) % MOD;
            suf[j] = (suf[j + 1] * base + (ull)str[j]) % MOD;
        }
    }
    // 判断[l, r]子串是否是回文
    bool isPalindrome(int l, int r) {
        ull lef = hashL(l, r);
        ull rig = hashR(l, r);
        return lef == rig;
    }
} my_str;

9.3 KMP算法

vector<int> GetPre(string &s){
    int n = s.length();
    vector<int> nxt(n, 0);
    int j = 0;
    for(int i = 1; i < n; i++){
        j = nxt[i - 1];
        while(j > 0 && s[i] != s[j]){
            j = nxt[j - 1];//上一项的前后缀刚好不等处
        }
        if(s[i] == s[j]) j++;
        nxt[i] = j;
    }
    return move(nxt);
}


vector<int> KMP(string &s, string &patt){
    int siz1 = s.size(), siz2 = patt.size();
    string temp = patt + "!" + s;
    vector<int> nxt = GetPre(temp), ans;

    for(int i = 2 * siz2 - 1; i < nxt.size(); i++){
        if(nxt[i] == siz2){
            ans.push_back(i - 2 * siz2);
        }
    }
    return move(ans);
}

9.4 Manacher算法

计算字符串的最长回文子串长度。线性dp，从对称中心向两边扩展。

int manacher(string &s) {
    string t = "^ ";
    for (auto c : s) t += c, t += " ";
    t += "!";
    int n = (int)t.size();
    vector<int> p(n, 0);
    int c = 0, r = 0; // c为当前中心，r为当前中心的最右边界
    for (int i = 1; i < n - 1; ++i) {
        if (i <= r) p[i] = min(r - i, p[2*c - i]);
        while (t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > r) r = i + p[i], c = i;
    }
    return *max_element(p.begin(), p.end());
}