今天模拟赛考的题，本来想写个暴力优化一下就跑路的

结果没超时，数组越界丢了 10pts

Description

求出现次数不少于 $k$ 次的最长的子串的长度。

Solution

最基本的暴力是枚举每一个字串再暴力判断，复杂度大概是 $\mathcal O(n^4)$，显然过不去，考虑优化。

发现暴力判断的时候可以用 哈希 或 kmp 优化，考场上忘记 kmp 怎么写了，就写了哈希，复杂度变为 $\mathcal O(n^3)$。

首先可以发现这个长度具有单调性，所以我们可以二分从当前最优的答案往后暴力拓展，没必要再从 $1$ 重新开始枚举，复杂度变为 $\mathcal O(n^2)$。

然后就可以过去了

可能说的有些不太清楚，具体还是看代码吧

Code

这是考后重写的一份代码，完全没有卡常，可读性更高因为考试的代码太丑了

最下面有一份考试时的代码

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n,m,ans,a[20005];
ull mul[20005],hs[20005];
int main(){
    cin>>n>>m;
	for(int i=1;i<=n;i++){
	    cin>>a[i];
	}
	mul[0]=1;
	for(int i=1;i<=n;i++){
	    mul[i]=mul[i-1]*19260817;//预处理
	}
	for(int i=1;i<=n;i++){
	    hs[i]=hs[i-1]*19260817+a[i];//哈希
	}
	for(int k=1;k<=n;k++){//从每一个位置开始枚举，往后拓展的长度为ans
	    while(1){//暴力拓展答案
	        int cnt=0;//记录出现的次数
	        for(int i=k;i<=n&&i+ans<=n;i++){//注意这里不要越界了！！1（模拟赛的时候就被这里坑了）
	            if(hs[i+ans]-hs[i-1]*mul[ans+1]==hs[k+ans]-hs[k-1]*mul[ans+1]){//判断
	                cnt++;
	            }
	        }
	        if(cnt>=m){
	            ans++;
	        }
	        else{//根据单调性，如果这个不满足，那么后面的一定不满足
	            break;
	        }
	    }
	}
    cout<<ans;
}

赛后改的赛时的垃圾代码

出现至少 𝑘 次意味着后缀排序后有至少连续 𝑘 个后缀以这个子串作为公共前缀．

所以，求出每相邻 𝑘 −1 个 ℎ𝑒𝑖𝑔ℎ𝑡 的最小值，再求这些最小值的最大值就是答案．

可以使用单调队列 𝑂(𝑛) 解决，但使用其它方式也足以 AC．

#include <cstring>
#include <iostream>
#include <set>

using namespace std;

constexpr int N = 40010;

int n, k, a[N], sa[N], rk[N], oldrk[N], id[N], px[N], cnt[1000010], ht[N], ans;
multiset<int> t;  // multiset 是最好写的实现方式

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int i, j, w, p, m = 1000000;

  cin >> n >> k;
  --k;

  for (i = 1; i <= n; ++i) cin >> a[i];  // 求后缀数组
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = a[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w <<= 1, m = p) {
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }

  for (i = 1, j = 0; i <= n; ++i) {  // 求 height
    if (j) --j;
    while (a[i + j] == a[sa[rk[i] - 1] + j]) ++j;
    ht[rk[i]] = j;
  }

  for (i = 1; i <= n; ++i) {  // 求所有最小值的最大值
    t.insert(ht[i]);
    if (i > k) t.erase(t.find(ht[i - k]));
    ans = max(ans, *t.begin());
  }

  cout << ans;

  return 0;
}