就下面的这种写法,为什么不越界呢?
它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; }
全部评论
(2) 回帖