1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
| #include <bits/stdc++.h> using namespace std; #define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout) #define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++) #define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++) #define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--) #define DEBUG(x) cerr<<#x<<"="<<x<<endl #define all(x) (x).begin(),(x).end() #define cle(x) memset(x,0,sizeof(x)) #define lowbit(x) ((x)&-(x)) #define ll long long #define ull unsigned ll #define db double #define lb long db #define pb push_back #define mp make_pair #define fi first #define se second inline int read() { int x=0; char ch=getchar(); bool f=0; for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48); return f?-x:x; } #define CASET fo(___,1,read()) const int N=200010; const int S=26;
namespace SAM{ int ne[N][S],fa[N],len[N],las,siz,idx[N]; inline void init() { for(int i=1;i<=siz;i++) memset(ne[i],0,sizeof(ne[i])),fa[i]=len[i]=0; las=siz=1; } inline void extend(int c,int id) { int cur=++siz; idx[cur]=id+1; len[cur]=len[las]+1; int p=las; for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur; if(!p) fa[cur]=1; else { int q=ne[p][c]; if(len[q]==len[p]+1) fa[cur]=q; else { int clone=++siz; len[clone]=len[p]+1; idx[clone]=idx[q]; memcpy(ne[clone],ne[q],sizeof(ne[q])); fa[clone]=fa[q]; for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=clone; fa[cur]=fa[q]=clone; } } las=cur; } }
int n,m,sum[N],val[30]; ll k; char s[N]; int L[N],R[N],id[N]; inline ll get() { ll ss=0; m=SAM::siz; fo(i,2,SAM::siz) id[i]=SAM::idx[i],L[i]=SAM::len[SAM::fa[i]]+1,R[i]=SAM::len[i],ss+=SAM::len[i]-SAM::len[SAM::fa[i]]; return ss; }
inline ll check(int x) { ll ss=0; fo(i,2,m) if(sum[id[i]]-sum[id[i]-L[i]]<=x) { int l=L[i],r=R[i],mid; for(;l<=r;) { mid=(l+r)>>1; if(sum[id[i]]-sum[id[i]-mid]<=x) l=mid+1; else r=mid-1; } ss+=(r-L[i]+1); } return ss; } int main() { CASET { n=read(); cin>>k; scanf("%s",s); SAM::init(); ff(i,0,strlen(s)) SAM::extend(s[i]-'a',i); fo(i,0,25) val[i]=read(); if(get()<k) { puts("-1"); continue; } fo(i,1,n) sum[i]=sum[i-1]+val[s[i-1]-'a']; int l=0,r=n*100,mid; for(;l+1<r;) { mid=(l+r)>>1; if(check(mid)>=k) r=mid; else l=mid; } printf("%d\n",r); } return 0; }
|