841. String hash

Given a length of n String , Re given m A asked , Each query contains four integers l1,r1,l2,r2, Please judge [l1,r1] and [l2,r2] Whether the strings and substrings contained in these two intervals are exactly the same .

The string contains only uppercase and lowercase English letters and numbers .

Input format
The first line contains integers n and m, Represents the length of the string and the number of queries .

The second line contains a length of n String , The string contains only uppercase and lowercase English letters and numbers .

Next m That's ok , Each line contains four integers l1,r1,l2,r2, Indicates the two intervals involved in a query .

Be careful , The position of the string is from 1 Numbered starting .

Output format
Output a result for each query , If two string substrings are identical, output Yes, Otherwise output No.

Each result takes up one line .

Data range
1≤n,m≤105
sample input ：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
sample output ：
Yes
No
Yes

Ideas ：
①、 String subscript from 1 Start
②、 First , The given string , Press the subscript to find from left to right i Is the last string , Find its character based ascii code , be based on P Hexadecimal accumulated string hash value
③、 Based on empirical values , A string of hash value , With 2⁶⁴ Data size for storage , With 131 perhaps 13331 When it is a decimal number , Cumulative hash It's worth it 2⁶⁴ modulus , The probability of conflict is very small , Think ignore
④、unsigned long long just 2⁶⁴, use ull For storage , If the data overflows , That is, high-order truncation , Keep it low , It's equivalent to automatic Yes 2⁶⁴ modulus
⑤、 The key point of the algorithm is the prefix of string hash Value preprocessing and p^i Array preprocessing
seek A string l~r Corresponding hash value , It only needs h[r] - h[l-1] * p[(r-1) - (l-1-1)] namely h[r] - h[l-1] * p[r-l+1]
Example ：123456
seek 34 Of hash value
1234 - 12 * 10^2 == 34

#include <iostream>
#include <cstring>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;
// Empirical value   Use 131 perhaps 13331  Use 2^64 To store the size of the string hash value , Theoretically   With 131 perhaps 13331 For the string of hexadecimal numbers hash value  mod 2^64  The probability of conflict after that is very small , It can be seen that there is no conflict 

ULL h[N], p[N];//h The array stores the string before the subscript hash value ,p The array stores the bit weight of the subscript position base 
char s[N];

int main()
{
    
    int n, m;
    cin>> n >> m >> s+1;

    // Find the string of hash Value preprocessing results   and   Subscript to be i The position of the corresponding p^i
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
    
        p[i] = p[i-1] * P;// Find the subscript i need × Bit weight of  p^0 p^1 p^2 p^3 1 1*p 1*p*p 1*p*p*p
        h[i] = h[i-1] * P + s[i];// Find out i The position corresponds to hash value ,ULL After spilling , High truncation , Keep it low , It's equivalent to 2^64 modulus ,s[i] The actual value is the hash value of the character 
    }

    int l1,r1,l2,r2;
    while(m -- )
    {
    
        cin>>l1>>r1>>l2>>r2;
        ULL x = h[r1] - h[l1-1] * p[r1-l1+1];  // Find a string hash value ,r1 Corresponding hash value  - (l1-1) Corresponding hash value  * p^(r1-l1+1)  namely   The difference between the two positions p^(r1-1 - (l1-1-1))
        ULL y = h[r2] - h[l2-1] * p[r2-l2+1];
        if(x == y)cout<<"Yes"<<endl;        // If the hash values of two strings are equal , Then the strings are equal 
        else cout<<"No"<<endl;
    }

    return 0;
}