题目描述

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数n和m，表示字符串长度和询问次数。

第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。

接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从1开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤n,m≤105

样例

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

算法1

(暴力)

（暴力会超时，有一个数据不能通过）

用到c++中的substr

basic_string substr( _Off = 0, _Count ) ;

参数：

_Off

所需的子字符串的起始位置。字符串中第一个字符的索引为 0,默认值为0.

_Count

复制的字符数目

返回值

一个子字符串，从其指定的位置开始

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    string str;
    cin>>str;string cmp1,cmp2;
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;

        cmp1=str.substr(l1-1,(r1-l1+1)); 
        cmp2=str.substr(l2-1,(r2-l2+1));
    if(cmp1==cmp2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }


    return 0;
}

算法2

(字符串哈希)

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
//由于前缀值的值会很大所以应该将数组中的数据定义为ULL型实现自动取余的效果
const int N=100010,P=131;//131为经验值,即p=131时哈希冲突最小。
//将字符串转换为131进制
//131的意义：代表该位置可以容纳的ASCII值可以达到131
int n,m;
char str[N];
ULL h[N],p[N];//h[]存放字符串的前缀值,p[]存放各个位数的相应权值

ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
//左面高位，右面低位，因为减法求差值部分时需要高位对齐
//所以1到l-1位类比于十进制中后面填零向左移动，即乘以相差位数的权值
int main()
{
    cin>>n>>m;
    cin>>str+1;
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+str[i];//计算字符串的前缀
        //过程：前一个状态左移一位，加上该状态的字符值
        p[i]=p[i-1]*P;//计算该状态的权值，即十进制中零的个数
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    }
    return 0;
}