题意 : 给出一个长度为 N 的序列，再给出一个 K 要求求出出现了至少 K 次的最长可重叠子串的长度
分析 : 后缀数组套路题，思路是二分长度再对于每一个长度进行判断，判断过程就是对于 Height 数组进行限定长度的分组策略，如果有哪一组的个数 ≥ k 则说明可行！
分组要考虑到一个事实，对于每一个后缀，与其相匹配能够产生最长的LCP长度的串肯定是在后缀数组中排名与其相邻。
一开始对分组的理解有误，所以想了一个错误做法 ==>
遍历一下 Height 将值 ≥ （当前二分长度） 的做一次贡献即 cnt++ ，若最后 cnt ≥ K 说明可行。当然这个肯定是炸了.......
下面说说我对于 Height 分组的理解吧，就看上面的图，如果当前 K == 2，那么第一组的含义是什么？换句话说就是为什么那么些个后缀要属于一组？可以看出第一组里面的 Height 值都不会小于 K ，实际的意义呢应当是第一组里面的有一个长度为 2 （不小于K）的共同前缀，即 “aa” ，那么是不是 “aa” 这个子串可重叠地出现了 cnt 次（cnt为第一组的后缀个数），可能你已经有点体会到分组的意义了！那么有没有可能有些前缀是 “aa” 但是没有被分进第一组呢？看见上面红字描述的事实么？根据上面的那个事实，而且 Height 的下标是根据排名有序的这个特点（有序的意思就是从小到大遍历 Height 实际传进去的下标就是排名！即 Height[i]，i是表示第 i 名的后缀），我们就知道这样的事情不会发生，且分出来的组肯定的“连续的块”，即不会有这一组的元素在其他地方的可能性！
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
;
int sa[maxn], s[maxn], wa[maxn], Ws[maxn], wv[maxn], wb[maxn];
int Rank[maxn], height[maxn];
bool cmp(int r[], int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; }
void da(int r[], int sa[], int n, int m)
{
int i, j, p, *x = wa, *y = wb;
; i < m; ++i) Ws[i] = ;
; i < n; ++i) Ws[x[i]=r[i]]++;
; i < m; ++i) Ws[i] += Ws[i-];
; i >= ; --i) sa[--Ws[x[i]]] = i;
, p = ; p < n; j *= , m = p)
{
, i = n - j; i < n; ++i) y[p++] = i;
; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
; i < n; ++i) wv[i] = x[y[i]];
; i < m; ++i) Ws[i] = ;
; i < n; ++i) Ws[wv[i]]++;
; i < m; ++i) Ws[i] += Ws[i-];
; i >= ; --i) sa[--Ws[wv[i]]] = y[i];
, x[sa[]] = , i = ; i < n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;
}
}
void calheight(int r[], int sa[], int n)
{
;
; i <= n; ++i) Rank[sa[i]] = i;
; i < n; height[Rank[i++]] = k)
, j = sa[Rank[i]-]; r[i+k] == r[j+k]; k++);
}
bool IsOk(int len, int n, int aim)
{
;
// for(int i=2; i<=n; i++){ //错误的！
// if(height[i] >= len)
// if(++cnt >= aim)
// return true;
// }return false;
; i<=n; i++){
if(height[i] >= len){ if(++cnt >= aim) return true; }
;
}return false;
}
int arr[maxn];
int main(void)
{
int N, K;
while(~scanf("%d %d", &N, &K)){
; i<N; i++)
scanf("%d", &arr[i]);
da(arr, sa, N+, );
calheight(arr, sa, N);
, R = N, ans = -;
while(L <= R){
);
;
;
}
ans==-? puts(") : printf("%d\n", ans);
}
;
}
题目单个元素的值能达到 1e6 这么大，数组按这个开还勉强OK，但是这里还是要学学离散化的姿势！
离散化版:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
;
struct st{
int ord, val;
bool operator < (const st &rhs) const {
return this->val < rhs.val;
};
}arr[maxn];
int sa[maxn], s[maxn], wa[maxn], Ws[maxn], wv[maxn], wb[maxn];
int Rank[maxn], height[maxn];
bool cmp(int r[], int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; }
void da(int r[], int sa[], int n, int m)
{
int i, j, p, *x = wa, *y = wb;
; i < m; ++i) Ws[i] = ;
; i < n; ++i) Ws[x[i]=r[i]]++;
; i < m; ++i) Ws[i] += Ws[i-];
; i >= ; --i) sa[--Ws[x[i]]] = i;
, p = ; p < n; j *= , m = p)
{
, i = n - j; i < n; ++i) y[p++] = i;
; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
; i < n; ++i) wv[i] = x[y[i]];
; i < m; ++i) Ws[i] = ;
; i < n; ++i) Ws[wv[i]]++;
; i < m; ++i) Ws[i] += Ws[i-];
; i >= ; --i) sa[--Ws[wv[i]]] = y[i];
, x[sa[]] = , i = ; i < n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;
}
}
void calheight(int r[], int sa[], int n)
{
;
; i <= n; ++i) Rank[sa[i]] = i;
; i < n; height[Rank[i++]] = k)
, j = sa[Rank[i]-]; r[i+k] == r[j+k]; k++);
}
bool IsOk(int len, int n, int aim)
{
;
; i<=n; i++){
if(height[i] >= len)
{ if(++cnt >= aim) return true; }
;
}return false;
}
int r[maxn];
int main(void)
{
int N, K;
while(~scanf("%d %d", &N, &K)){
; i<N; i++){
scanf("%d", &arr[i].val);
arr[i].ord = i;
}
;
sort(arr, arr+N);
; i<N; i++)
&& arr[i].val == arr[i-].val) r[arr[i].ord] = num; ///注意相等的时候如何处理
else r[arr[i].ord] = ++num;
da(r, sa, N+, num+);
calheight(r, sa, N);
, R = N, ans = -;
while(L <= R){
);
;
;
}
ans==-? puts(") : printf("%d\n", ans);
}
;
}