专栏文章

哈希！！！

qq1uple
P4482题解参与者 10已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@miqaox62
此快照首次捕获于
2025/12/04 01:42
3 个月前
此快照最后确认于
2025/12/04 01:42
3 个月前
查看原文
题目链接
主播觉得什么后缀状物和神秘 Border 理论根本无法战胜，于是直接哈希！！！
本题解不需要任何 Border 的性质！！！
暴力哈希非常简单 (直接枚举 Border 长度)，但是根本就过不了啊，我们要考虑优化。
我们发现我们实际上有很多相同的东西，我们本可以预处理出来但是还要跑，浪费了很多时间。
我们肯定要预处理一些东西，我们设一个阈值 SS，我们对于字符串 SS 中的 Sl…l+S−1S_{l \dots l+S-1}，将相同的都放在一起一个集合 (用一个 vector 维护所有的集合)，对于每次询问，小于阈值 SS 直接跑暴力就行了，我们来考虑大于阈值 SS 的情况，我们在之前维护的集合中二分找到区间里面的下标，直接枚举所有合法的就行了，看似上很暴力，但是实际上字符集只有 2626，所以很难卡掉吧，复杂度不敢下定论，有人分析一下吗。
阈值随便取几百几千就行了，下面是代码核心部分
CPP
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]));
}

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...