bzoj 4560 字符串覆盖

Posted on | Views:

字符串 $hash$ + 贪心 + $dp$ .

  • 首先可以字符串 $hash$ 预处理出 $N$ 个串各自可以放的位置 (用开头的位置表示) ,以及 $L_{i,j} ,R_{i,j}$ 分别表示从位置 $j$ 往左/右边找,能找到的第一个可以放第 $i$ 个串的位置(不包含 $j$ ).
  • 求最大值,可以贪心.首先枚举这 $N$ 个串放置的 $N!$ 种顺序,依次选择位置.分两种情况,记上个串结束位置为 $p$ ,若与上个串相交,则放在 $L_{i,p}$ 最优,若与上个串不相交,则放在 $R_{i,p}$ 最优.这个决策也可以大力枚举.这一步的时间复杂度 $O(N!\cdot 2^N)$
  • 求最小值,不相交时贪心放在 $R_{i,p}$ 不一定最优,考虑 $dp$ .
  • 仍然枚举 $N!$ 种放置顺序,设 $f(i,j)$ 表示考虑了前 $j$ 个位置,下一个放置的应该是第 $i$ 个串.
  • 若不放第 $i$ 个串,则转移到 $f(i,j+1)$ .
  • 若放第 $i$ 个串,若它与上一个串不相交,转移到 $f(i+1,j+Len(i))$ .否则放在匹配 $j$ 后能放的第一个位置.
  • 这一步时间复杂度 $O(N!\cdot N\cdot Len(A))$ ,也是总的时间复杂度.
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
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e4+10;
const ull Base=37;
int n,N,len[5];
ull Hash[MAXN],pw[MAXN];
char A[MAXN],B[5][MAXN];
void Init_Hash()
{
	Hash[0]=0;
	for(int i=1;i<=n;++i)
		Hash[i]=Hash[i-1]*Base+(ull)(A[i]-'a');
}
ull Calc_Hash(int l,int r)
{
	return Hash[r]-Hash[l-1]*pw[r-l+1];
}
int L[5][MAXN],R[5][MAXN],f[5][MAXN];
int id[5];
int DP(int i,int j)
{
	if(i>N)
		return 0;
	j=R[id[i]][j];
	if(j==0)
		return n+1;
	if(f[i][j]!=-1)
		return f[i][j];
	int &ans=f[i][j];
	ans=DP(i,j+1);
	int k=j+len[id[i]],st=j;
	++i;
	for(;i<=N;++i)
	{
		ans=min(ans,DP(i,k)+k-j);
		int p=R[id[i]][j];
		if(p<st || p>=k)
			return ans;
		st=p;
		k=max(k,st+len[id[i]]);
	}
	ans=min(ans,k-j);
	return ans;
}
int dfs(int i,int j)
{
	if(i>N)
		return 0;
	j=R[id[i]][j];
	if(!j)
		return 0;
	int k=j+len[id[i]],st=j;
	int ans=0;
	++i;
	for(;i<=N;++i)
	{
		ans=max(ans,dfs(i,k)+k-j);
		int p=L[id[i]][k];
		if(p<st || p>=k)
			return ans;
		st=p;
		k=max(k,st+len[id[i]]);
	}
	ans=max(ans,k-j);
	return ans;
}
int main()
{
	pw[0]=1;
	for(int i=1;i<=10000;++i)
		pw[i]=pw[i-1]*Base;
	int T=read();
	while(T--)
	{
		scanf("%s",A+1);
		n=strlen(A+1);
		N=read();
		for(int i=1;i<=N;++i)
		{
			scanf("%s",B[i]+1);
			len[i]=strlen(B[i]+1);
		}
		Init_Hash();
		memset(L,0,sizeof L);
		memset(R,0,sizeof R);
		for(int i=1;i<=N;++i)
		{
			ull val=0;
			for(int j=1;j<=len[i];++j)
				val=val*Base+(B[i][j]-'a');
			for(int j=1;j+len[i]-1<=n;++j)
				if(Calc_Hash(j,j+len[i]-1)==val)
					L[i][j]=j;
				else
					L[i][j]=L[i][j-1];
			for(int j=n+1-len[i];j>=1;--j)
				if(Calc_Hash(j,j+len[i]-1)==val)
					R[i][j]=j;
				else
					R[i][j]=R[i][j+1];
		}
		for(int i=1;i<=N;++i)
			id[i]=i;
		int minans=n+1,maxans=0;
		do
		{
			memset(f,-1,sizeof f);
			minans=min(minans,DP(1,1));
			maxans=max(maxans,dfs(1,1));
		}while(next_permutation(id+1,id+1+N));
		printf("%d %d\n",minans,maxans);
	}
	return 0;
}