luogu p2582(字尾陣列)

2022-11-27 10:57:45 字數 838 閱讀 6948

傳送門

給你一個字串\(str\),問出現次數為\(k\)的最長的子串的長度。

首先我們先將字串\(str\)的所有字尾進行排序,並求出他們兩兩的\(height\)陣列。

根據\(height\)陣列的含義,\(height[i]=lcp(i,i-1)\),我們知道,倘若存在一個子串出現了k次,那麼必定存在一個連續的區間\([l,r],(r-l+1 \ge k-1)\),使得\(lcp(l,r) !=0\)。那麼我們他們\(lcp\)中的最小值就是答案。因此我們發現,我們現在要求的是\(height\)陣列中,長度至少為\(k-1\)的最小值,並要使得最小值最大化。而這個顯然是一個經典的劃窗問題,我們可以通過單調佇列在\(\mathcal(n)\)的時間複雜度中求出答案。

故整體的複雜度為\(\mathcal(nlogn)\)

#include #define maxn 20010

using namespace std;

int rk[maxn],sa[maxn],height[maxn],tmp[maxn],cnt[maxn],n,k;

int str[maxn],tot=0;

unordered_mapmp;

unordered_mapvis;

void sa(int n,int m)

//get height

i=0,k=0,height[0]=0;

for(j=rk[0];ique;

int res=0;

for(int i=1;i<=n;i++)

printf("%d\n",res);

return 0;

}