牛客练习赛61 相似的子串（二分+Hash）

题面在此

题解：将字符串分成k部分，然后求最长前缀，所以我们只关注前缀部分就好了，公共前缀后边的是啥不用管，那么问题就转化成了是否存在k个不相交的字符串的最长公共前缀问题。首先用Hash来记录一下字符串，然后再二分枚举最长前缀的长度。怎么样才能保证不相交呢？可以用map记录一段字符串的右边界。然后当这个串再次出现时，判断当前的左边界和上次的右边界时候相交。。这里要用无序map，否则会T，也可以用ull对Hash自动取余。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=2e5+;

char s[N];

ll Hash[N],p[N];

ll mod=1e9+;

ll base=;

ll n,m;

unordered_map<ll ,ll >mp1,mp2;

ll getHash(ll x,ll y){

    return (Hash[y]%mod-Hash[x-]*p[y-x+]%mod+mod)%mod;

}

bool check(ll x){

    mp1.clear();mp2.clear();

    for(int i=x;i<=n;i++){

        ll tmp=getHash(i-x+,i);

        if(mp1[tmp]==) {

            mp1[tmp]=i;

            mp2[tmp]++;

        }

        else if(mp1[tmp]<=i-x) {

            mp1[tmp]=i;mp2[tmp]++;

        }

        if(mp2[tmp]>=m) return ;

    }

    return ;

}

int main(){

    cin>>n>>m;

    scanf("%s",s+);

    p[]=;

    for(ll i=;i<=n;i++){

        Hash[i]=((Hash[i-]*base)%mod+s[i]-'a')%mod;

        p[i]=p[i-]*base%mod;

    }

    ll ans=;

    ll l=,r=n;

    while(l<=r){

        ll mid=(l+r)/;

        if(check(mid)){

            ans=max(ans,mid);

            l=mid+;

        }

        else r=mid-;

    }

    cout<<ans<<endl;

    return ;

}

巴特西

牛客练习赛61 相似的子串（二分+Hash）

最新文章

热门文章