NC5026E

题意

把原题意转化为给你一个长为 $n$ 的字符串，求至少有 $k$ 个相同且不相交的长为 $x$ (可为 $0$ )的子串， $x_{max}$ 为多少？

思路

二分+哈希字符串 时间复杂度 $O(nlogn)$
这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。
那么如何验证？首先预处理字符串Hash得到
Hash数组表示对应的Hash值
power数组表示对应的 $base^{length_i}$
有一个难点在于如何保证不相交？

我们在map的value中放入一个pair<int,int>，first放该字符串的结尾位置，second放该字符串的出现次数，当出现新的相同的hash值(相同的字符串)时我们验证新的位置减去上一个的位置是否 $\geq x$ ，若满足则更新最后一次出现且满足的位置，并增加满足的数量。

tips: $unordered\_map$ 查询复杂度为 $O(1)$ ， $map$ 查询复杂度为 $O(logn)$
这里用map我跑了一下没挂，但是理论上来说是可以挂的。

上面是map 下面是unoreder_map

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int n,k;
char s[N];
unordered_map<unsigned long long,pair<int,int> > mp;
unsigned long long Hash[N],power[N],base=131;

bool check(int x){
    mp.clear();
    for(int i=x;i<=n;i++){
        unsigned long long h=Hash[i]-Hash[i-x]*power[x];
        if(i-mp[h].first>=x) mp[h].first=i,mp[h].second++;
        if(mp[h].second>=k) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>s+1;
    power[0]=1;
    for(int i=1;i<=n;i++){
        Hash[i] =Hash[i-1]*base+s[i]-'a'+1;
        power[i]=power[i-1]*base;
    }
    int L=0,R=n/k+1,ans=0;
    while(L<R){
        int mid=L+(R-L)/2;
        if(check(mid)) L=mid+1,ans=mid;
        else R=mid;
    }
    cout<<ans<<'\n';
    return 0;
}