Template <字符串哈希>-526互联

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ULL = unsigned long long;

// 字符串哈希（注意 get(l,r)为闭区间，字符串下标从1开始）
struct StringHash
{
    vector<ULL> h;  // 哈希数组
    vector<ULL> p;  // p[i] = P^i
    int n;          // 字符串长度
    ULL P;          // 进制数
    StringHash(string _s, ULL _P = 131)
    {
        P = _P;
        init(_s);
    }
    void init(string const &s)
    {
        n = s.size();
        h = vector<ULL>(n + 1);
        p = vector<ULL>(n + 1);
        h[0] = 0;
        p[0] = 1;
        for (int i = 1; i <= n; i ++)
        {
            p[i] = p[i-1] * P;
            h[i] = h[i-1] * P + s[i-1];
        }
    }
    ULL get(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    
};

int main()
{
    int T;
	cin >> T;
    string s;
	cin >> s;
	StringHash h(s);
    int l1, l2, r1, r2;
    while (cin >> l1 >> r1 >> l2 >> r2)
    {
        cout << h.get(l1, r1) << ", " << h.get(l2, r2) << ", ";
        if (h.get(l1, r1) == h.get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}