题解 P3435 【[POI2006]OKR-Periods of Words】

发现这道水题，网上还没有题解用哈希。 ~~（本萌新不会kmp） ~~ 那我就补发一篇hash的题解 其实判断前缀很好想 只要考虑怎么判断后缀即可 看A是不是QQ的前缀 就是判断A-Q与Q的对应部分是不是相等即可 答案具有单调性，满足二分条件 用线段树维护区间最值即可 时间复杂度（nlogn） 注意哈希要用unsigned long long的自然溢出 unsigned int 很容易被卡hash WA。。。 字符串里hash还是很好用的 但是KMp千万不要像我这种萌新一样不会啊。。。。 ```cpp //code by luotc #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ull unsigned long long const int maxn=1e6+5,base=131; int n,tree[maxn<<2]; ull hsh[maxn],bas[maxn]; char s[maxn]; ull ans; inline bool check(int ll,int rr){ return (hsh[rr-ll+1]==hsh[rr]-hsh[ll-1]*bas[rr-ll+1]); } inline void update(int k,int l,int r,int L,int R,int dat){ if(L==l&&r==R){ tree[k]=max(tree[k],dat); return; } if(R<=mid) update(lson,L,R,dat); else if(L>mid) update(rson,L,R,dat); else update(lson,L,mid,dat),update(rson,mid+1,R,dat); } inline int query(int k,int l,int r,int pos){ if(l==r) return tree[k]; if(pos<=mid) return max(tree[k],query(lson,pos)); else return max(tree[k],query(rson,pos)); } int main(){ cin>>n; cin>>(s+1); for(int i=1;i<=n;i++) hsh[i]=hsh[i-1]*base+s[i]-'a'; bas[0]=1; for(int i=1;i<=n;i++) bas[i]=bas[i-1]*base; // cout<<check(3,4)<<endl; for(int i=1;i<n;i++){ int l=i+1,r=min(n,2*i),ret=0; while(l<=r){ if(check(i+1,mid)) ret=mid,l=mid+1; else r=mid-1; } // cout<<i<<' '<<ret<<endl; if(ret!=0) update(1,1,n,i+1,ret,i); } for(int i=2;i<=n;i++) ans+=query(1,1,n,i); cout<<ans<<endl; return 0; } ```