首页 > 代码库 > 【bzoj4310】跳蚤 后缀数组+二分

【bzoj4310】跳蚤 后缀数组+二分

题目描述

很久很久以前,森林里住着一群跳蚤。一天,跳蚤国王得到了一个神秘的字符串,它想进行研究。
首先,他会把串分成不超过 k 个子串,然后对于每个子串 S,他会从S的所有子串中选择字典序最大的那一个,并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。
现在他想找一个最优的分法让“魔力串”字典序最小。

输入

第一行一个整数 k。
接下来一个长度不超过 105 的字符串 S。

输出

输出一行,表示字典序最小的“魔力串”。

样例输入

13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba

样例输出

cbc


题解

后缀数组+二分

先使用后缀数组求出sa、rank和height,然后预处理出ST表,用倍增RMQ求LCP(再次height的定义,height[i][j]表示sa[i]与sa[i-(1<<j)]的LCP

然后我们二分答案串在S的所有子串中的排名。

这里用到了一个挺好理解的结论:一个串的本质不同的子串的个数为$\sum\limits_{i=1}^nn-sa[i]-height[i]$,就是某个字符开头的串的个数-重复出现过的串的个数。

有个这个结论可以做点什么?首先我们可以确定二分边界。

然后我们还可以根据子串的排名mid来求出对应的子串。

怎么求?我们从前往后枚举i,算出以sa[i]开头的本质不同的子串个数n-sa[i]-height[i],如果mid大于这个数就将mid减去这个数,否则对应的子串就是sa[i]开头,sa[i]+height[i]-1+mid结尾的字符串。退推一下,应该不是很难想。

那么有了子串以后,我们在原串上从后往前贪心,每次找到一个字符,就比较当前串和二分的子串的字典序大小关系,如果当前的子串字典序较大,则在这个找到的字符后面分割一下。最后比较分割次数与k的关系即可。

需要注意的是二分的子串必须大于等于单个的最大字符,否则无论怎样分割都不可能分割出小于等于该串的字符串。

#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;typedef long long ll;int sa[N] , r[N] , ws[N] , wa[N] , wb[N] , rank[N] , height[N][20] , n , m = 27 , log[N] , k , L , R;char str[N];void getsa(){	int i , j , p , *x = wa , *y = wb;	for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ;	for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];	for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i;	for(p = j = 1 ; p < n ; j <<= 1 , m = p)	{		for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i;		for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j;		for(i = 0 ; i < m ; i ++ ) ws[i] = 0;		for(i = 0 ; i < n ; i ++ ) ws[x[y[i]]] ++ ;		for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];		for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[y[i]]]] = y[i];		for(swap(x , y) , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ )		{			if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = p - 1;			else x[sa[i]] = p ++ ;		}	}	for(i = 1 ; i < n ; i ++ ) rank[sa[i]] = i;	for(p = i = 0 ; i < n - 1 ; height[rank[i ++ ]][0] = p)		for(p ? p -- : 0 , j = sa[rank[i] - 1] ; r[i + p] == r[j + p] ; p ++ );}void query(ll mid){	int i;	for(i = 1 ; i <= n ; i ++ )	{		if(n - sa[i] - height[i][0] < mid) mid -= n - sa[i] - height[i][0];		else		{			L = sa[i] , R = sa[i] + height[i][0] + mid - 1;			return;		}	}	L = 0 , R = n - 1;}int lcp(int x , int y){	if(x == y) return n;	x = rank[x] , y = rank[y];	if(x > y) swap(x , y);	int k = log[y - x];	return min(height[y][k] , height[x + (1 << k)][k]);}bool cmp(int l1 , int r1 , int l2 , int r2){	int t = lcp(l1 , l2) , len1 = r1 - l1 + 1 , len2 = r2 - l2 + 1;	if(len1 <= len2 && len1 <= t) return 1;	if(len1 > len2 && len2 <= t) return 0;	if(len1 <= t && len2 <= t) return len1 <= len2;	return r[l1 + t] <= r[l2 + t];}bool judge(){	int i , cnt = 1 , last = n - 1;	for(i = n - 1 ; ~i ; i -- )	{		if(r[i] > r[L]) return 0;		if(!cmp(i , last , L , R)) cnt ++ , last = i;		if(cnt > k) return 0;	}	return 1;}int main(){	int i , j;	ll lp = 1 , rp = 0 , mid , ans;	scanf("%d%s" , &k , str) , n = strlen(str);	for(i = 0 ; i < n ; i ++ ) r[i] = str[i] - ‘a‘ + 1;	n ++ , getsa() , n -- ;	for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;	for(i = 1 ; (1 << i) <= n ; i ++ )		for(j = (1 << i) ; j <= n ; j ++ )			height[j][i] = min(height[j][i - 1] , height[j - (1 << (i - 1))][i - 1]);	for(i = 1 ; i <= n ; i ++ ) rp += n - sa[i] - height[i][0];	while(lp <= rp)	{		mid = (lp + rp) >> 1 , query(mid);		if(judge()) ans = mid , rp = mid - 1;		else lp = mid + 1;	}	query(ans);	for(i = L ; i <= R ; i ++ ) putchar(str[i]);	return 0;}

 

 

【bzoj4310】跳蚤 后缀数组+二分