题解 | #字串比较#

暴力做法：

切割出s1的[l1,r1]子串 ，再切割出s2的[l2,r2]子串，比较两个子串的字典序

优化

利用字符串哈希，可以在o(1)复杂度判断某两个子串是否相等。二分出第一个不匹配的字母

代码如下：

#include<bits/stdc++.h>
#define ull unsigned long long
#define endl "\n"
using namespace std;
const int N=2e5+10,P=131;
ull h1[N],h2[N],p[N];
int n,m,q;
int l1,r1,l2,r2;
string s1,s2;
ull get1(int x,int y)
{
    return h1[y]-h1[x-1]*p[y-x+1];
}
ull get2(int x,int y)
{
    return h2[y]-h2[x-1]*p[y-x+1];
}
bool check(int x)
{
    if(get1(l1,x)==get2(l2,l2+x-l1)) return true;
    else return false;
}
int main()
{
    cin>>n>>m>>q;
    cin>>s1>>s2;
    s1="#"+s1;
    s2="#"+s2;
    p[0]=1;
    for(int i=1;i<=N-1;i++)
    {
        p[i]=P*p[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        h1[i]=h1[i-1]*P+s1[i];
    }
    for(int i=1;i<=m;i++)
    {
        h2[i]=h2[i-1]*P+s2[i];
    }
    while(q--)
    {
        
        cin>>l1>>r1>>l2>>r2;
        int l=l1,r=r1;
        while(l<r)//二分查找第一个不匹配的字母
        {
            int mid=(l+r)/2;
            if(check(mid)) l=mid+1;
            else r=mid;
        }
        if(s1[l]==s2[l2+l-l1]) cout<<"="<<endl;
        else if(s1[l]>s2[l2+l-l1]) cout<<">"<<endl;
        else cout<<"<"<<endl;
    }
}