为什么这种情况不算越界呢?

就下面的这种写法,为什么不越界呢?
它base可以无限乘的吗?????
乘了多次以后肯定超过INT_MAX或者小于INT_MIN了,为什么不报错????

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
const int base=0x3f3f3f3f;  //玄学数字,这个数可以降低重复率
int z[maxn],f[maxn],p[maxn],n;
char s[maxn];
int get1(int l,int r)
{
    return z[r]-z[l-1]*p[r-l+1];
}
int get2(int l,int r)
{
    return f[r]-f[l-1]*p[r-l+1];
}
//如果区间[l,r]的int正序逆序哈希值一样,那么这个区间就是回文串
bool check(int i,int j)
{
    if(get1(i,j)==get2(n-j+1,n-i+1))
        return true;
    return false;
}
int gethalf(int x){
    if(x%2==0) return x/2;
    else return x/2+1;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    p[0]=1;

    for(int i=1; i<=n; i++)
    {
        z[i]=z[i-1]*base-s[i];
        f[i]=f[i-1]*base-s[n+1-i];
        p[i]=p[i-1]*base;
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(check(1,i)&&check(1,gethalf(i))){
            res++;
        }
    }
    printf("%d",res);
    return 0;
}
全部评论
哈希 自然取模 没有哈希冲突就没问题
点赞 回复 分享
发布于 2021-03-30 16:56
还是不懂嗷,哪位大哥能讲明白的欢迎留言
点赞 回复 分享
发布于 2021-04-01 11:20

相关推荐

阿里淘天内蓷:虽然很想感谢你的分享,但是此刻的嫉妒和酸气已经涌上心头,所以我撤销一下对你的感谢吧,希望你能原谅我
点赞 评论 收藏
分享
08-23 10:20
湘南学院 Java
弓长门马:不要尬黑,这个公司桌子高,175以下坐下摸不到键盘
点赞 评论 收藏
分享
09-26 19:36
已编辑
西北大学 C++
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务