自动搬运

查看原文

来自洛谷，原作者为

	JoaoFelix c1c

搬运于2025-08-24 22:01:38，当前版本为作者最后更新于2020-07-05 12:01:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像还没有题解？来简要的写一下一篇不会证明的题解

我们可以把题目转化成两个不同的问题然后进行合并

第一个问题： 我们发现要求的是多串问题，然后这些串都要同时出现在一个串内，所以我们可以建出ac自动机，然后发现k<=6，因此可以状压出有没有出现过的状态，并且记录当前所在节点

第二个问题： 我们要求这个串是给出的两个串的公共子序列，然后这个我们可以考虑这是一个子序列自动机的裸题，只需要建出子序列自动机然后在自动机上遍历即可，记录在两个串上当前的位置就好了

所以综上所述要记录四个状态，第一个问题的两个和第二个问题的两个串的出现位置 我们发现这些状态之间的转移像是一个拓扑图，然后最长路转移就好了

然后发现状态数用数组记录不下，所以要用map，具体状态数不会太大（感性理解） 复杂度：O(能过)

代码：

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

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

const int N = 1805;

int n, m, k, ch[N][52], tot, fail[N], ed[N], ans;
int tsx[305][52], tsy[305][52], l[N], lst[52];
char strx[305], stry[305], str[305];

struct node {
	int px, py, u, mask;
	node(int cpx = 0, int cpy = 0, int cu = 0, int cmask = 0) {
		px = cpx, py = cpy, u = cu, mask = cmask;
	}
	bool operator < (const node &c) const {
		if (px != c.px) return px < c.px;
		if (py != c.py) return py < c.py;
		if (u != c.u) return u < c.u;
		return mask < c.mask;
	}
};
map<node, int> stp; map<node, bool> inq;

int Type(char c) {
	if (c >= 'a' && c <= 'z') return c - 'a';
	return c - 'A' + 26;
}

#define SS ch[u][i]
void BFS() {
	queue<int> que; while (!que.empty()) que.pop();
	for (int i = 0; i < 52; i++) if (ch[0][i]) que.push(ch[0][i]);
	while (!que.empty()) {
		int u = que.front(); que.pop();
		for (int i = 0; i < 52; i++)
			if (!SS) SS = ch[fail[u]][i];
			else que.push(SS), fail[SS] = ch[fail[u]][i], ed[SS] |= ed[fail[SS]];
	}
}

void DP() {
	queue<node> que; while (!que.empty()) que.pop();
	stp[node(0, 0, 0, 0)] = 1; que.push(node(0, 0, 0, 0)), inq[node(0, 0, 0, 0)] = true;
	while (!que.empty()) {
		node now = que.front(); que.pop(); inq[now] = false;
		int ntp = stp[now];
		int px = now.px, py = now.py, u = now.u, mask = now.mask;
		if (mask == (1 << k) - 1) ans = max(ans, ntp);
		for (int i = 0; i < 52; i++) {
			int nx = tsx[px][i], ny = tsy[py][i], v = ch[u][i], nsk = mask | ed[v];
			if (nx > n || ny > m) continue; node to = node(nx, ny, v, nsk);
			if (!stp[to] || stp[to] < ntp + 1) {
				stp[to] = ntp + 1;
				if (!inq[to]) que.push(to);
			}
		}
	}
}

int main() {
	n = read(); m = read(); k = read();
	for (int i = 1; i <= k; i++) l[i] = read();
	scanf("%s", strx + 1), scanf("%s", stry + 1);
	for (int i = 0; i < 52; i++) lst[i] = n + 1;
	for (int i = n; i >= 0; i--) {
		for (int j = 0; j < 52; j++) tsx[i][j] = lst[j];
		lst[Type(strx[i])] = i;
	}
	for (int i = 0; i < 52; i++) lst[i] = m + 1;
	for (int i = m; i >= 0; i--) {
		for (int j = 0; j < 52; j++) tsy[i][j] = lst[j];
		lst[Type(stry[i])] = i;
	}
	for (int i = 1; i <= k; i++) {
		scanf("%s", str + 1); int u = 0;
		for (int j = 1; j <= l[i]; j++) {
			int p = Type(str[j]);
			if (!ch[u][p]) ch[u][p] = ++tot;
			u = ch[u][p];
		}
		ed[u] |= (1 << i - 1);
	}
	BFS(), DP();
	printf("%d\n", ans - 1);
	return 0;
}