哈希！！！

q1uple · 2025-02-09 20:15:13 · 题解

题目链接

主播觉得什么后缀状物和神秘 Border 理论根本无法战胜，于是直接哈希！！！

本题解不需要任何 Border 的性质！！！

暴力哈希非常简单 (直接枚举 Border 长度)，但是根本就过不了啊，我们要考虑优化。

我们发现我们实际上有很多相同的东西，我们本可以预处理出来但是还要跑，浪费了很多时间。

我们肯定要预处理一些东西，我们设一个阈值 S，我们对于字符串 S 中的 S_{l \dots l+S-1}，将相同的都放在一起一个集合 (用一个 vector 维护所有的集合)，对于每次询问，小于阈值 S 直接跑暴力就行了，我们来考虑大于阈值 S 的情况，我们在之前维护的集合中二分找到区间里面的下标，直接枚举所有合法的就行了，看似上很暴力，但是实际上字符集只有 26，所以很难卡掉吧，复杂度不敢下定论，有人分析一下吗。

阈值随便取几百几千就行了，下面是代码核心部分

ull hs[N],p[N];
const ull P=1331;
char s[N];
int n;
ull gv(int l,int r){
    return hs[r]-hs[l-1]*p[r-l+1];
}
map<ull,int>ma;
vector<int>pos[N];
const int len=3000;
int solve(int x,int y){
    if(y-x<=len+11){
        int l=1,r=y-x,ans=0;
        while(l<=r){
            int mid=r;
            if(gv(x,x+mid-1)==gv(y-mid+1,y))    qma(ans,mid),l=mid+1;
            else r--;
        }
        return ans;
    }
    int l=1,r=len+11,ans=0;
    while(l<=r){
        int mid=r;
        if(gv(x,x+mid-1)==gv(y-mid+1,y))    qma(ans,mid),l=mid+1;
        else r--;
    }
    ull now=gv(x,x+len-1);
    l=0,r=pos[ma[now]].size()-1;
    int be=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(x<pos[ma[now]][mid])   be=mid,r=mid-1;
        else l=mid+1;
    }
    if(be==-1)   return max(ans,(int)(s[x]==s[y]));
    for(int i=be;i<pos[ma[gv(x,x+len-1)]].size();i++){
        int now=pos[ma[gv(x,x+len-1)]][i];
        if(now+len-1>y)   break;
        int len=y-now+1;
        if(gv(x,x+len-1)==gv(now,y)){
            qma(ans,len);  return ans;
        }
    }
    return max(ans,(int)(s[x]==s[y]));
}