1.暴力

#include<iostream>
#include<string.h>
#include<string>
using namespace std;


int main()
{
   string str;
   int n,m;
   cin >> n >> m ;
   cin>>str;
   int l1,r1,l2,r2;
    while(m--)
    {
        cin>>l1>>r1>>l2>>r2;
        int n1=r1-l1,n2=r2-l2;
        if(n1!=n2)
        {
            cout<<"No"<<endl;
        }
        while(l1<=r1)
        {
            if(str[l1-1]!=str[l2-1])
            {
                cout<<"No"<<endl;
                break;
            }
            l1++;l2++;
        }
        if(l1>r1) cout<<"Yes"<<endl;

    }
    return 0;
}

结果TLE了。复杂度是O(mn)

2.字符串哈希

#include<iostream>
#include<string.h>
#include<string>
using namespace std;
const int   P=131,N=1e5+3;
unsigned long long p[N],h[N];

int main()
{
    int n,m;
    cin>>n>>m;
    char *str=new char[n];
    scanf("%s",str);

   //计算p[k]=p^k,h[k]
   p[0]=1;h[0]=0;
   for(int i=1;i<=n;i++)
   {
       p[i]=p[i-1]*P;
       h[i]=h[i-1]*P+str[i-1];
   }
   int l1,r1,l2,r2;
   while(m--)
   {
       cin>>l1>>r1>>l2>>r2;
       if((l1==l2)&&(r1==r2))
       {
           cout<<"Yes"<<endl;
           continue;
       }
       unsigned long long hash1,hash2;
       hash1=h[r1]-h[l1-1]*p[r1-l1+1];//****//
       hash2=h[r2]-h[l2-1]*p[r2-l2+1];
       if(hash1==hash2) cout<<"Yes"<<endl;
       else cout<<"No"<<endl;
   }

    return 0;
}