2021暑假 HDU中超 第四场 1004

Display Substring

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1055 Accepted Submission(s): 212

题意

给一个字符串，告知每个小写字母对应的价值，求价值和第k名的子串

Sample Input

2
5 5
ababc
3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 15
ababc
3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output

4
-1

考场思路：

求第k小子串，那么构建后缀自动机

根据传统算法搞（记录SAM上每个节点出发能到达的节点数），突然意识到不对劲

这里的第k小是指权值和第k小，而不是字典序

不能像传统算法那样，依据第一位转移

补题：

题目不要求输出子串是什么，只需要输出第k大子串的权值

可以考虑二分答案，假设 \(w\)​ ​为答案，然后需要check是否有k个子串权值小于等于 \(w\)

先回顾一下SAM的性质：

每个节点代表一个等价类，其父节点包含的最大子串为AAA

则这个节点包含形如 XXXAAA，XXAAA，XAAA的子串

我们要计算每个节点中有多少子串的权值是大于 \(w\)​ 的，并且同一个节点中的子串都连续

权值和显然单调，可以对每个节点再二分，利用前缀和计算答案

check复杂度 \(O(nlogn)\)​ ，总复杂度 \(O(nlognlogn)\)​ ​​

#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
#define fff(x,y,z) for(int x=y;x<=z;x++)
#ifdef ACM_LOCAL
const int maxn = 100005;
#else
const int maxn = 100005;
#endif
int mode=1e9+7;
void swap(int &a, int &b){int ins=a;a=b;b=ins;}

struct node{
    int ch[29];
    int fa, len, cnt;
    int fir;
    void clear(){
        for(int i=0;i<28;i++) ch[i] = 0;
        fa = len = fir = 0;
    }
}sam[2*maxn];

int n; ll k;
string s;
int tot, lst;
int val[28], sum[maxn];

void expend(int c){
    int cur = ++tot;
    int p = lst;
    lst = cur;
    sam[cur].len = sam[p].len+1;
    sam[cur].cnt = 1;
    sam[cur].fir = sam[cur].len;

    while(!sam[p].ch[c]){
        sam[p].ch[c] = cur;
        p = sam[p].fa;
        if(p == -1){
            sam[cur].fa = 0;
            return;
        }
    }

    int q = sam[p].ch[c];
    if(sam[p].len+1 == sam[q].len){
        sam[cur].fa = q;
    }else{
        int clo = ++tot;
        sam[clo] = sam[q];
        sam[clo].len = sam[p].len+1;
        sam[clo].fir = sam[q].fir;
        sam[clo].cnt = 0;
        sam[q].fa = clo;
        sam[cur].fa = clo;
        while(p != -1 && sam[p].ch[c] == q){
            sam[p].ch[c] = clo;
            p = sam[p].fa;
        }
    }
}

void init(){
    for(int i=0;i<n*2+5;i++) sam[i].clear();
    sam[0].len = 0;
    sam[0].fa = -1;
    sam[0].cnt = 0;
    tot = 0;
    lst = 0;
}

bool check(int w, ll k){
    //if (numof x<=w) >= k
    ll res = 0;
    for(int i=1;i<=tot;i++){
        int fs = sam[i].fir;//endpos
        int l = fs - sam[i].len + 1, r = fs - sam[sam[i].fa].len, mid;
        while(l < r){
            mid = (l+r)/2;
            if(sum[fs] - sum[mid-1] <= w){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        if(sum[fs] - sum[l-1] <= w) res += fs - sam[sam[i].fa].len - l + 1;
    }
    return res >= k;
}

void solve(){
    cin >> n >> k;
    cin >> s;
    for(int i=0;i<26;i++) cin >> val[i];
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + val[s[i-1] - 'a'];

    init();
    for(int i=0;i<n;i++) expend(s[i] - 'a');

    int l = 0, r = sum[n], mid;
    while(l < r){
        mid = (l+r)/2;
        if(check(mid, k)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    if(check(l, k)) cout << l << '\n';
    else cout << "-1\n";

}

signed main() {
#ifdef ACM_LOCAL
    freopen("x.txt","r",stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}