Interval_hash

const int L = 1e6 + 5;//长度上限，这里一般够用
const int HASH_CNT = 2;//双哈希
struct StringHash_interval {
    int hashBase[HASH_CNT] = {29, 31};//哈希种子，可以用131, 13331
    int hashMod[HASH_CNT] = {int(1e9 + 9), 998244353};//任意选择一个较大的质数来约束大小
    char s[L];
    int ls;
    int hsh[HASH_CNT][L];
    int pwMod[HASH_CNT][L];

    void init() {  // 初始化
        ls = 0;
        for (int i = 0; i < HASH_CNT; ++i) {
            hsh[i][0] = 0;
            pwMod[i][0] = 1;
        }
    }

    StringHash_interval() { init(); }

    //这里使用的版本时串的前面的幂次大大大大,并且时从1开始的
    void extend(char c) {//后面添加
        s[++ls] = c;                          // 记录字符数和每一个字符
        for (int i = 0; i < HASH_CNT; ++i) {  // 双哈希的预处理
            pwMod[i][ls] = 1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // 得到b^ls
            hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
        }
    }

    vector<int> getHash(int l, int r) {  // 得到哈希值
        vector<int> res(HASH_CNT, 0);
        for (int i = 0; i < HASH_CNT; ++i) {
            int t = (hsh[i][r] - 1ll * hsh[i][l - 1] * pwMod[i][r - l + 1]) % hashMod[i];
            t = (t + hashMod[i]) % hashMod[i];//负数变为正数
            res[i] = t;
        }
        return res;
    }
};