題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串 $s$，每個字母都有一個權值，現在要求所有本質不同子串中權值和第 $k$ 大的權值

題目分析：如果沒有本質不同，那有一個很簡單的二分套二分的方法，就是直接二分答案，每次枚舉字符串中的每個后綴的位置作為左端點，然后二分右端點的位置，判斷一下小于等于 $mid$ 的子串個數和 $k$ 的關系，正確性是顯然的

但本題要求本質不同的子串，不難聯想到后綴數據結構，我用的是后綴自動機。在后綴自動機中，每個節點代表的實質上就是一個本質不同的子串，而其形式一般表示為 $Suffix(T,i)+S$，其中 $T$ 是原串的一個后綴，$Suffix(T,i)$ 是 $T$ 的一個前綴，同時 $S$ 是其 $link$ 指針所指的字符串，所以每個節點表示的子串實質上也就是 $Suffix(T,i)$ 的這么一段。

為了方便去檢查，我們不妨對于每個節點記錄一下其 $last$ 指針所在的位置記為 $pos[last]=i$，也就是該子串在原串中對應的位置。這樣后綴自動機上 $last$ 節點對應在原串上的字符串就是：右端點為 $i$，左端點屬于 $[i?len[last]+1,i?len[link[last]]]$ 的這么一段了

說了這么多，其實本題只需要將最開始二分套二分的思路，搬到后綴自動機上去 $check$ 就可以啦

有個小細節需要注意一下，可能某個后綴的 $pos[last]$ 已經更新了，但是其 $link[last]$ 并沒有及時更新，所以最后需要在 $parerent$ 樹上 $dfs$ 一下，具體就是令 $pos[link[last]]=pos[last]$，即讓 $pos$ 沒有更新的后綴隨便選擇一個后代更新就可以了，顯然是正確的

還有一個坑點，$k$ 會爆 $int$

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; char s[N]; int val[26]; int tot,last,pos[N<<1],sum[N]; vector<int>node[N<<1]; struct Node {int ch[26];int fa,len; }st[N<<1]; inline int newnode() {tot++;for(int i=0;i<26;i++)st[tot].ch[i]=0;st[tot].fa=st[tot].len=pos[tot]=0;node[tot].clear();return tot; } void add(int x) {int p=last,np=last=newnode();st[np].len=st[p].len+1;while(p&&!st[p].ch[x])st[p].ch[x]=np,p=st[p].fa;if(!p)st[np].fa=1;else{int q=st[p].ch[x];if(st[p].len+1==st[q].len)st[np].fa=q;else{int nq=newnode();st[nq]=st[q]; st[nq].len=st[p].len+1;st[q].fa=st[np].fa=nq;while(p&&st[p].ch[x]==q)st[p].ch[x]=nq,p=st[p].fa;//向上把所有q都替換成nq}} } LL check(int limit) {LL cnt=0;for(int i=1;i<=tot;i++) {int p=pos[i],l=st[st[i].fa].len+1,r=st[i].len,len=-1;while(l<=r) {int mid=(l+r)>>1;if(sum[p]-sum[p-mid]<=limit) {len=mid;l=mid+1;} else {r=mid-1;}}if(len!=-1) {cnt+=len-st[st[i].fa].len;}}return cnt; } void dfs(int u) {for(auto v:node[u]) {dfs(v);}if(!pos[u]) {pos[u]=pos[node[u][0]];} } void init() {last=1;tot=-1;newnode();newnode(); } int main() { #ifndef ONLINE_JUDGE// freopen("C:\\Users\\Frozen_Guardian\\Desktop\\1004.in","r",stdin);// freopen("C:\\Users\\Frozen_Guardian\\Desktop\\1004.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {init();int n;LL k;scanf("%d%lld",&n,&k);scanf("%s",s+1);for(int i=0;i<26;i++) {scanf("%d",val+i);}for(int i=1;i<=n;i++) {add(s[i]-'a');sum[i]=sum[i-1]+val[s[i]-'a'];pos[last]=i;}for(int i=1;i<=tot;i++) {node[st[i].fa].push_back(i);}dfs(1);int l=1,r=sum[n],ans=-1;while(l<=r) {int mid=(l+r)>>1;if(check(mid)>=k) {ans=mid;r=mid-1;} else {l=mid+1;}}printf("%d\n",ans);}return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的HDU多校4 - 6988 Display Substring(后缀自动机+二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。