[数据结构与算法]LEETCODE周赛记录287

区间哈希+二分做法

• 哈希魅力在于能快速判断两个字符串是否相同
• 维护前缀哈希值，计算s的每个区间的哈希
• 对每个s的后缀，由于从某个点开始往前全部满足公共前缀，某个点往后不满足公共前缀，故可使用二分查找最后一个满足条件的点。
• 判断字符串是否符合条件使用区间哈希

typedef long long LL;
typedef unsigned long long ULL;
const int N = 100010, P = 13331;

class Solution {
public:
    ULL h[N], p[N];

    ULL get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    // 原串的前缀[1, len] 是否与 s.substr(base, len) 相等
    bool check(int base, int len) {
        return get(1, len) == get(base, base + len - 1);
    }

    LL sumScores(string s) {
        int n = s.size(); s = ' ' + s;
        p[0] = 1;
        for(int i = 1; i <= n; i ++) {
            h[i] = h[i - 1] * P + s[i];
            p[i] = p[i - 1] * P;
        }

        LL res = 0;
        for(int i = n; i >= 1; i --) {
            int l = 0, r = n - i + 1;       // 二分长度
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(check(i, mid)) l = mid;
                else r = mid - 1;
            }
            res += r;
        }
        return res;
    }
};

扩展KMP（Z算法模板题）$O(n)$

• 详情Z算法

• 解空间划分不当使问题变复杂
• eg:010使用中间的数1划分要比使用左右的数划分来得更简单