题目描述

给定一个长度为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

输出样例:

Yes
No
Yes
1、trie树字符串

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
int q[N][26],cnt[N];
int n,idx;
char str[N];
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int k=str[i]-'a';
        if(!q[p][k]) q[p][k]=++idx;
        p=q[p][k];
    }
    cnt[p]++;
}
bool find(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int k=str[i]-'a';
        if(q[p][k]==0)  return false;
        p=q[p][k];
    }
    if(cnt[p]==0)  return false;
    return true;
}
int main()
{
    scanf("%d",&n);

    while(n--)
    {
        char op[2];
        scanf("%s",op);
        if(*op=='I')
        {
            cin>>str;
            insert(str);
        }
        else
        {
            cin>>str;
            if(find(str))  cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        memset(str,0,sizeof str);
    }
    return 0;
}

2、p进制

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10;
ull q[N],h[N];
int n,m,p=131;
char str[N];
ull get(int l,int r)
{
    return h[r]-h[l-1]*q[r-l+1];
}
int main()
{
    scanf("%d%d%s",&n,&m,str+1);

    q[0]=1;
    for(int i=1;i<=n;i++)  
    {
        q[i]=q[i-1]*p;
        h[i]=h[i-1]*p+str[i];
    }

    while(m--)
    {

        int l1,l2,r1,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1)==get(l2,r2))   cout<<"YES"<<endl;
        else  cout<<"NO"<<endl;
    }
    return 0;
}