[26. String hash]

summary

• Where strings are used, you can generally use KMP Algorithm . use KMP Algorithms can generally use string hashing . The code is simpler .（ Special hash method , String prefix hashing ）
• Turn a string into a p Hexadecimal Numbers （ Hash value ）, Mapping different strings to different numbers .（ Comparing whether the prefixes of two interval strings are equal becomes comparing whether the hashes of two interval strings are the same ）

The core

• With a K Hexadecimal angle , Let's treat strings as numbers .

Ideas

• Hash the prefix of each string （ Preprocess prefix hash ）
• Hash the interval string , Use the formula to calculate the hash value of the string interval
• Calculate whether the two interval strings are equal, and convert it into whether the hash values of the two strings are equal

Two questions :

problem 1： How do we define the hash value of a prefix

• To form such as X₁X₂X₃⋯X_{n - 1}X_n String , In characters ascii Code times P To the power of .
• Mapping formula ：(X₁×P^{n- 1}+X₂×P^{n- 2}+⋯+X_{n -1}×P¹+X_n×P⁰) mod Q

character string str = "ABCAB"
character string str The prefix is AABABCABCA hypothesis A~Z Map to subscript 1 ~ 26.
h[0] = 0
h[1] = "A" Of hash value
h[2] = "AB" Of hash value
h[3] = "ABC" Of hsah value
h[4] = "ABCA" Of hash value
Prefix ABCA Hash value of = (1 2 3 1 )_p = (1 * p³ + 2 * p² + 3 * p¹ + 1 * p⁰)

step

1. Think of strings as p Binary number , String has 10 Letters , As 10 digit
2. hold p Convert a decimal number to a decimal number
3. Put the calculated number on a smaller number Q（ Put any string , Map to from 0 The natural number of the beginning ）

matters needing attention ：

• Any character cannot be mapped to 0, Otherwise, different strings will be mapped to 0 The situation of , such as A,AA,AAA All are 0
• The question of conflict ： Through clever settings P (131 or 13331) , Q (2⁶⁴) Value , There is little conflict at this time .

problem 2： What is the use of prefix hashes

• You can use prefix hash to calculate the hash of any substring through a formula

The problem is to compare whether the substrings of different intervals are the same , Whether the corresponding hash value is the same .

• Finding the hash value of a string is equivalent to finding the prefix and , Finding the hash value of the substring of a string is equivalent to finding the partial sum .

Prefixes and formulas : h[ i + 1]=h[i] × P + str[i] i∈[0,n−1]i∈[0,n−1] h Prefix and array ,str For string array

Interval and formula :h[l,r]=h[r]−h[l−1]×Pr−l+1

Understanding of intervals and formulas : ABCDE And ABC The first three character values of are the same , Just two ,
Multiply P2P2 hold ABC Turn into ABC00, Reuse ABCDE - ABC00 obtain DE Hash value of .

subject

Given a length of n String , Re given m A asked , Each query contains four integers l1,r1,l2,r2, Please judge [l1,r1][l1,r1] and [l2,r2][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≤10₅

sample input ：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

sample output ：

Yes
No
Yes

Code

#include <iostream>
using namespace std;

using ULL = unsigned long long;
//typedef unsigned long long ULL;

const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];   //p[] Mainly several powers 

// h[i] front i A character hash value 
//  The string becomes a p Hexadecimal Numbers , Embodies the character + The order , You need to make sure that different strings correspond to different numbers 
// P = 131  or  13331 Q=2^64, stay 99% There will be no conflict 
//  Use scenarios ：  Whether the substrings of two strings are the same 

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

int main()
{
    
    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;      // String from 1 Numbered starting ,h[1] Is the hash value of the previous character 
    h[0] = 0;
    for (int i = 1; i <= n; i ++)
    {
    
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];   // Prefix and hash the entire string 
       
    }
    while (m --)
    {
    
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2) )puts("Yes");
        else puts("No");
    }
   
    return 0;
}