*II. P3269 [JLOI2016]字符串覆盖

摘自 贪心专题 第三部分例题 II.

神仙思维题。一个时空复杂度均非常优秀的解法。

显然对于最大值和最小值需要分开计算。首先我们求出一些基础的东西辅助解题：$n$ 个子串 $s_i$ 的 next 数组（KMP）以及与母串 $T$ 在每个位置的匹配情况。这个可以在 $\mathcal{O}(nL)$ 的时间内预处理出来。

最大值

遇到这种题目我们似乎无从下手，那么尝试把 $n=4$ 作为突破口。考虑 $n!$ 枚举钦定每个字符串出现位置按开头从左到右的顺序，那么一个贪心的想法是把出现顺序在前面的字符串尽量往前放。但这样有个问题，就是在放第 $i$ 个字符串时有两种情况：是否与 $s_{i-1}$ 重叠，因为两种情况都有可能成为最优解（反例容易举出）。但若确定了是哪种情况，贪心策略就保证了方案唯一：若不重叠，则越往前放越好（给剩下来的字符串留足空间）；若重叠则越往后放越好（因为不劣）。因此再 $2^{n-1}$ 枚举相邻的两个字符串是否重叠即可。注意统计答案是不应只关注前一个字符串，因为可能出现 $l_1<l_2<r_2<l_3<r_3<r_1$ 的情况，其中 $l_i,r_i$ 是 $s_i$ 在 $T$ 中的出现位置，因此需记录的是当前所有字符串的右端点最大值即 $\max r_i$。时间复杂度 $\mathcal{O}(n!2^nnL)$。

当然可以更优：用 $\log$ 级别的查找即 lower_bound 代替线性查找即可做到 $\mathcal{O}(nL+n!2^nn\log L)$。

最小值

一个显然的想法是舍弃所有被其它字串覆盖的子串，若相同则仅保留一个，因为要使答案最小让其被完全覆盖一定最优。那么剩下来的子串就一定满足若 $l_i<l_j$ 则一定有 $r_i<r_j$，这是很强的一个性质，并且结合最优化的限制，给予我们动态规划的思想：设 $f_{i,S}$ 表示前 $i$ 位放置了集合 $S$ 内的子串的最小值且第 $i$ 位被覆盖，转移时枚举 $p\in S$ 且 $s_p$ 与 $T$ 在 $i$ 处匹配。分两种情况讨论，一种是与已放置字符串有交集，另一种是不交，综合一下转移方程如下：

$$\mathrm{checkmin}(f_{i,S},\min_{p\in S}\min_{0\leq j<i}f_{j,S\backslash p}+\min(len_p,i-j))$$

当 $j>i-len_p$ 时 $i-j<len_p$ 故进行贡献为 $len_p$ 的转移不会使答案变得更小（即更优），而当 $j\leq i-len_p$ 时 $i-j>len_p$ 所以进行贡献为 $i-j$ 的转移也不会影响答案，因此可以看做对于每个 $j\in [0,i)$ 都进行 $len_p$ 和 $i-j$ 的转移。$len_p$ 可以通过直接记录 $f_{i,S}$ 前缀最小值优化，而 $i-j$ 的转移可以设 $g_{i,S}$ 表示 $\min_{j=0}^if_{j,S}-j$ 进行优化。再加上滚动数组，本部分时间复杂度 $\mathcal{O}(n2^nL)$，空间复杂度更是仅有惊人的 $\mathcal{O}(2^n)$！

也许你会问：直接用求最小值的 DP 求最大值不就行了吗？非也，因为转移方程中 $\min(len_p,i-j)$ 的部分并没有变成 $\max$，故此时 $len_p$ 只能从 $j\leq i-len_p$ 转移，而 $i-j$ 只能从 $j>i-len_p$ 转移，所以需要加一个线段树维护区间修改与区间最值，很麻烦，不如直接贪心更方便。而且一道题目锻炼两种思维，岂不妙哉？

复杂度分析：本题的时间复杂度为 $\mathcal{O}(n!n2^n\log L+n2^nL)$，空间复杂度为 $\mathcal{O}(nL+2^n)$。很显然后者已经达到了理论下界。实现起来不算麻烦，而且效率非常优秀，以 33ms 的极限速度与仅仅 900K 的空间占用夺得最优解。

#include <bits/stdc++.h>
using namespace std;

#define mem(x, v, s) memset(x, v, sizeof(x[0]) * (s))
template <class T1, class T2> void cmin(T1 &a, T2 b){a = a < b ? a : b;}
template <class T1, class T2> void cmax(T1 &a, T2 b){a = a > b ? a : b;}

const int N = 1e4 + 5;
char t[N], s[4][N];
int n, tL, len[4], nxt[4][N];
bool mat[4][N];
void KMP(char *s, int sL, int *nxt, bool *mat) {
	for(int i = 2; i <= sL; i++) {
		nxt[i] = nxt[i - 1];
		while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]];
		if(s[nxt[i] + 1] == s[i]) nxt[i]++;
	}
	for(int i = 1, p = 0; i <= tL; i++) {
		while(p && s[p + 1] != t[i]) p = nxt[p];
		if(s[p + 1] == t[i]) p++;
		if(p == sL) mat[i] = 1, p = nxt[p];
		else mat[i] = 0;
	}
}

bool OverLap(char *t, char *s, int tL, int sL, int *nxt) {
	for(int i = 1, p = 0; i <= tL; i++) {
		while(p && s[p + 1] != t[i]) p = nxt[p];
		if(s[p + 1] == t[i]) p++;
		if(p == sL) return 1;
	}
	return 0;
}

int GetMax() {
	if(n == 1) return len[0];
	static int id[4], ans, pos[4][N], cnt[4]; ans = 0, mem(cnt, 0, 4);
	for(int i = 0; i < n; i++) id[i] = i;
	for(int i = 0; i < n; i++) for(int j = 1; j <= tL; j++) if(mat[i][j]) pos[i][cnt[i]++] = j - len[i];
	do {
		for(int S = 0; S < 1 << n - 1; S++) {
			int cur = -1, res = 0, rbound = 0;
			for(int bit = 0; bit < n; bit++) {
				int i = id[bit];
				if(!bit) {cur = pos[i][0], rbound = cur + len[i] - 1, res = len[i]; continue;}
				int p = -1, pr = id[bit - 1];
				if(S >> bit - 1 & 1) {
					int rlim = min(tL - len[i] + 1, cur + len[pr] - 1);
					int it = upper_bound(pos[i], pos[i] + cnt[i], rlim) - pos[i];
					if(it == 0 || pos[i][it - 1] < cur) break;
					p = pos[i][it - 1];
				}
				else {
					int it = lower_bound(pos[i], pos[i] + cnt[i], cur + len[pr]) - pos[i];
					if(it == cnt[i]) break;
					p = pos[i][it];
				}
				res += max(0, p + len[i] - 1 - max(rbound, p - 1));
				cmax(rbound, p + len[i] - 1), cur = p;
			}
			cmax(ans, res);
		}
	} while(next_permutation(id, id + n));
	return ans;
}

int GetMin() {
	if(n == 1) return len[0];
	static int ban[4], id[4], m; mem(ban, 0, 4), m = 0;
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
		if(strcmp(s[i] + 1, s[j] + 1)) ban[j] |= OverLap(s[i], s[j], len[i], len[j], nxt[j]);
	for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) ban[j] |= !strcmp(s[i] + 1, s[j] + 1);
	for(int i = 0; i < n; i++) if(!ban[i]) id[m++] = i;
	static int f[2][16], g[2][16];
	mem(f, 0x3f, 2), mem(g, 0x3f, 2), f[0][0] = g[0][0] = 0;
	for(int i = 1, cur = 1, pr = 0; i <= tL; i++, swap(cur, pr)) {
		for(int j = 0; j < 1 << m; j++) {
			f[cur][j] = N;
			for(int k = 0; k < j; k++) {
				if(!(j >> k & 1)) continue;
				int S = j - (1 << k), p = id[k];
				if(mat[p][i]) cmin(f[cur][j], min(f[pr][S] + len[p], g[pr][S] + i));
			}
			g[cur][j] = min(g[pr][j], f[cur][j] - i), cmin(f[cur][j], f[pr][j]);
		}
	}
	return f[tL & 1][(1 << m) - 1];
}

void solve() {
	scanf("%s %d", t + 1, &n), tL = strlen(t + 1);
	for(int i = 0; i < n; i++) {
		scanf("%s", s[i] + 1);
		KMP(s[i], len[i] = strlen(s[i] + 1), nxt[i], mat[i]);
	}
	cout << GetMin() << " " << GetMax() << "\n";
}

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

启示：在时间复杂度可以承受的前提下尽可能确定更多信息，也许其所带来的重要性质使 DP 或贪心变得可行。