文章目录

• • 题意
  • 题解

接上次FFT之后,我们又遇到了一道后缀自动机题.

题意

给出一个字符串和 26 26 26个字母的花费,求总花费第 k k k小的不重复子串的花费,如果找不到第 k k k小的子串,输出 − 1 -1 −1.

题解

子串不能重复,显然是用后缀数据结构处理.对原字符串 s s s求出花费的前缀和并构建后缀自动机.二分答案并在后缀自动机上二分判断答案是否符合要求,复杂度 n l o g 2 n nlog^2n nlog2n,时限稳够,只要注意多组数据下不要将数组都memset即可.
数据结构板子会用就行了,确实没什么好说的.

#include<bits/stdc++.h> //Ithea Myse Valgulious
typedef long long ll;
using namespace std;
const int yuzu=2e5;
typedef int fuko[yuzu|10];
typedef char fuka[yuzu|10];
fuko c;
struct suffix_automaton {
  fuko net[26],len,link,sum,pos; 
  vector<int> ch[yuzu|10];
  int cnt,lat;
  void clear(int n) {
    cnt=lat=0,*link=-1;
    for (int i=0;i<=(n<<1);++i) pos[i]=0;
    for (int i=0;i<=(n<<1);++i) 
      for (int j=0;j<26;++j) net[j][i]=0;
    for (int i=0;i<=(n<<1);++i) ch[i].clear();
  }
  void add(int c) {
    int p=lat,cur=lat=++cnt;
    len[cur]=len[p]+1;
    for (;~p&&!net[c][p];p=link[p]) net[c][p]=cur;
    if (!~p) { link[cur]=0; return; }
    int q=net[c][p];
    if (len[q]==len[p]+1) { link[cur]=q; return; } 
    int cl=++cnt,i;
    len[cl]=len[p]+1;
    for (i=0;i<26;++i) net[i][cl]=net[i][q];
    link[cl]=link[q],link[q]=link[cur]=cl;
    for (;~p&&net[c][p]==q;p=link[p]) net[c][p]=cl;
  } 
  void dfs(int u) {
    for (int v:ch[u]) dfs(v);
    if (!pos[u]) pos[u]=pos[ch[u][0]];
  }
  void add(char *s) {
    for (int i=1;s[i];++i) {
      sum[i]=sum[i-1]+c[s[i]-97];
      add(s[i]-97),pos[lat]=i;
    }
    for (int i=1;i<=cnt;++i) 
      ch[link[i]].push_back(i);
    dfs(0);
  }
  int cal(int x,ll k) {
    ll ans=0;
    for (int i=1;i<=cnt;++i) {
      int p=pos[i],l=p-len[i]+1,r=p-len[link[i]],mid;
      for (;l<r;sum[p]-sum[mid-1]<=x?r=mid:l=mid+1) mid=l+r>>1;
      if (sum[p]-sum[l-1]<=x) ans+=p-len[link[i]]-l+1;
    }
    return ans>=k;
  }
}zw;
fuka s;
int main() {
  int i,ca,n;
  for (scanf("%d",&ca);ca--;) {
    ll k;
    scanf("%d%lld%s",&n,&k,s+1);
    for (i=0;i<26;++i) scanf("%d",c+i);
    zw.clear(n),zw.add(s);
    int l=1,r=zw.sum[n],mid;
    for (;l<r;zw.cal(mid,k)?r=mid:l=mid+1) mid=l+r>>1;
    printf("%d\n",zw.cal(l,k)?l:-1);
  }
}

谢谢大家.