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

2019-09-25 09:23:54


发现这道水题,网上还没有题解用哈希。

~~(本萌新不会kmp) ~~

那我就补发一篇hash的题解

其实判断前缀很好想

只要考虑怎么判断后缀即可

看A是不是QQ的前缀

就是判断A-Q与Q的对应部分是不是相等即可

答案具有单调性,满足二分条件

用线段树维护区间最值即可

时间复杂度(nlogn)

注意哈希要用unsigned long long的自然溢出

unsigned int 很容易被卡hash WA。。。

字符串里hash还是很好用的

但是KMp千万不要像我这种萌新一样不会啊。。。。

//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;
}