[数据结构与算法]hduoj 6988 题解

题意：

一个字符串的每个字符都有独特的价值，一个字符串的价值为其所有字符的价值和，子串集为一个字符的所有子串的集合，现在要你求出一个字符串的价值第k小的子串的价值是多少

思路：
前缀知识需要后缀自动机，二分。
后缀自动机的每一个节点可看做一个子串集合，同时可以观察得到在确定好字符后，其后缀的价值具有单调性，因此可以对整体答案进行二分，再对每一个节点二分统计答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int maxc=26;
char s[maxn];
int val[maxc];
int sum[maxn];

int cal_sum(int l,int r){
    return sum[r]-sum[l-1];
}

struct Suffix_Automaton {
    int next[maxn<<1][maxc];
	int len[maxn<<1];
	int link[maxn<<1];
	int id=0;
	int last;
	ll endpos[maxn<<1];
	int a[maxn];
    int b[maxn<<1];
    int rpos[maxn<<1];
	void init() {
		for(int i=1; i<=id; i++){
			link[i] = len[i] = 0;
			memset(next[i],0,sizeof(next[i]));
			endpos[i]=0;
			a[i]=0;
			b[i]=0;
		}
		last = id = 1;
	}
	void add(int c,int pos) {
		int x = ++id;
		rpos[x] = pos;
		len[x] = len[last] + 1;
		endpos[x] = 1;
		int p;
		for (p = last; p && !next[p][c]; p = link[p])
			next[p][c] = x;
		if (!p){
			link[x] = 1;
	    }
		else {
			int q = next[p][c];
			if (len[p] + 1 == len[q]){
				link[x] = q;
			}
			else {
				int nq = ++id;
				len[nq] = len[p] + 1;
				link[nq] = link[q];
				memcpy(next[nq], next[q], sizeof(next[q]));
				rpos[nq] = rpos[q];
				for (; p&&next[p][c] == q; p = link[p])
					next[p][c] = nq;
				link[q] = link[x] = nq;
			}
		}
		last = x;
	}
	ll getSubNum() {
		ll ans = 0;
		for (int i = 2; i <= id; i++)
			ans += len[i]-len[link[i]];
		return ans;
	}
	void getTP(int Len){
	    for(int i=1;i<=id;i++) a[len[i]]++;
		for(int i=1;i<=Len;i++) a[i]+=a[i-1];
		for(int i=1;i<=id;i++) b[a[len[i]]--]=i;
	}
	int cal(int x,int p){
        int n = len[x] - len[link[x]];
        int l = rpos[x] - len[x] + 1;
        int r = l + n - 1;
        int L=l,R=r,mid;
        if(cal_sum(R,rpos[x])>p)
            return 0;
        while(L<R){
            mid = (L+R)>>1;
            if(cal_sum(mid, rpos[x])<=p)
                R=mid;
            else
                L=mid+1;
        }
        return r - L + 1;
	}
	int solve(int Len,ll k){
	    int r=sum[Len],l=1,mid;
	    while(l<r){
            int mid = (l+r)>>1;
            ll res = 0;
            for(int i=2;i<=id;i++)
                res += cal(i,mid);
            if(res<k)
                l = mid+1;
            else
                r = mid;
	    }
	    return l;
	}
} sam;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int len;
        ll k;
        scanf("%d%lld",&len,&k);
        scanf("%s",s+1);
        sam.init();
        for(int i=1;i<=len;i++)
            sam.add(s[i]-'a',i);
        sam.getTP(len);
        ll lim = sam.getSubNum();
        for(int i=0;i<maxc;i++)
            scanf("%d",&val[i]);
        if(k>lim){
            puts("-1");
            continue;
        }
        for(int i=1;i<=len;i++)
            sum[i] = sum[i-1]+val[s[i]-'a'];
        printf("%d\n",sam.solve(len,k));
    }
	return 0;
}
/*
3
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
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
*/