【bzoj5073】[Lydsy1710月赛]小A的咒语 后缀数组+倍增RMQ+贪心+dp

时间：2020-12-31 19:13:07

题目描述

给出 $A$ 串和 $B$ 串，从 $A$ 串中选出至多 $x$ 个互不重合的段，使得它们按照原顺序拼接后能够得到 $B$ 串。求是否可行。多组数据。

$T\le 10$ ，$|A|,|B|\le 10^5$ ，$x\le 100$ 。

题解

后缀数组+倍增RMQ+贪心+dp

设 $f[i][j]$ 表示从 $A$ 串的前 $i$ 个字符中选出 $j$ 段，能够拼出 $B$ 串的最大长度。

那么考虑转移，如果 $i+1$ 不用则 $f[i+1][j]\leftarrow f[i][j]$ ，否则枚举拼的长度 $k$ ，如果 $A_{i+1...i+k}=B_{f[i][j]+1...f[i][j]+k}$ 则 $f[i+k][j+1]\leftarrow f[i][j]+k$ 。

仔细想想后一步可以不用这样处理，可以直接贪心地选择LCP来拼接。因为选择LCP相比不选择，多拼接的一段和前面相连，相当于本身没有占用次数，不会存在更优解。

因此使用后缀数组+倍增RMQ维护LCP，设 $LCP(A_{i+1},B_{f[i][j]+1})=t$ ，则有转移 $f[i+t][j+1]\leftarrow f[i][j]+t$ 。

时间复杂度 $O(T(nx+n\log n))$ 。

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200010

using namespace std;

int sa[N] , r[N] , ws[N] , wa[N] , wb[N] , rank[N] , height[N] , mn[N][20] , log[N] , f[N][110];

char A[N] , B[N];

void init(int n , int m)

{

	int i , j , p , *x = wa , *y = wb;

	for(i = 0 ; i < m ; i ++ ) ws[i] = 0;

	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 ; 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 ; 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 = 0 ; i < n ; i ++ ) rank[sa[i]] = i;

	for(p = i = 0 ; i < n - 1 ; height[rank[i ++ ]] = p)

		for(p ? p -- : 0 , j = sa[rank[i] - 1] ; r[i + p] == r[j + p] ; p ++ );

	for(i = 1 ; i <= n ; i ++ ) mn[i][0] = height[i];

	for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;

	for(i = 1 ; (1 << i) <= n ; i ++ )

		for(j = 1 ; j + (1 << i) + 1 <= n ; j ++ )

			mn[j][i] = min(mn[j][i - 1] , mn[j + (1 << (i - 1))][i - 1]);

}

inline int lcp(int p , int q)

{

	p = rank[p] , q = rank[q];

	if(p > q) swap(p , q);

	p ++ ;

	int k = log[q - p + 1];

	return min(mn[p][k] , mn[q - (1 << k) + 1][k]);

}

int main()

{

	int T;

	scanf("%d" , &T);

	while(T -- )

	{

		int n , m , k , i , j , t;

		scanf("%d%d%d%s%s" , &n , &m , &k , A , B);

		for(i = 0 ; i < n ; i ++ ) r[i] = A[i] - 'a' + 1;

		for(i = 0 ; i < m ; i ++ ) r[i + n + 1] = B[i] - 'a' + 1;

		r[n] = 27 , r[n + m + 1] = 0 , init(n + m + 2 , 28);

		memset(f , 0 , sizeof(f));

		for(i = 0 ; i < n ; i ++ )

			for(j = 0 ; j <= k ; j ++ )

				f[i + 1][j] = max(f[i + 1][j] , f[i][j]) , t = lcp(i , f[i][j] + n + 1) , f[i + t][j + 1] = max(f[i + t][j + 1] , f[i][j] + t);

		for(i = 1 ; i <= k ; i ++ )

			if(f[n][i] == m)

				break;

		if(i <= k) puts("YES");

		else puts("NO");

	}

	return 0;

}

相关文章