题意：有 $n$ 个串只包含 A, B, C, D 的 $S_i$，问是否存在一个 $T$，经过删除 $T$ 中存在的 $S_i$ 直到不存在任意一个 $S_i$ 后，可以得到不同的串。$n, \sum |S_i|\leq 2\times 10 ^ 6$，8s。
神仙 AC 自动机 + Hash 随机化分析。
首先分析几个结论：
结论 1：如果一个 $S_i$ 被其他串组合后完全删除，那么这个串是没有意义的。
证明：显然如果要删这个串的话，可以删除组成他的所有串。
结论 2：如果一个 $S_i$ 被其他串所删除但是没有完全删除，那么答案一定是 Yes。
证明：直接取 $T = S_i$，至少会得到空串和没有完全删除的串，已经符合题目条件。
有了上面两个结论之后，我们可以通过使用 AC 自动机暴力匹配，用一个栈记录匹配过程，如果匹配到了一个串的话，直接倒回到还没有加入串前的状态。这样一定不会出现贪心匹配没有完全匹配的情况（即有其他方案使得该串被完全删除），因为一旦出现这种情况，答案就是 Yes。
下面所有的串一定不会出现一个是另一个子串的问题了。
再来一个结论：
结论 3：如果出现两个串 $S_i$ 和 $S_j$（$i, j$ 可能相同），$S_i$ 的某个后缀和 $S_j$ 的某个前缀是相同的，并且剩余部分不同，那么答案一定是 Yes。
证明：构造一个串为 $S_i$ 去掉相同后缀的前缀 + 共同后缀 / 前缀 + $S_j$ 去掉相同前缀的后缀。我们前面说到，不会再出现一个串是另一个子串的情况。那么 $S_i, S_j$ 分别删除后，剩下的两个串不同且无法消去，于是答案就是 Yes。
最后一个结论：
结论 4：不满足结论 3 的条件，答案一定是 No。
因为如果一个答案是 Yes 的话，一定出现了两个串相交的情形（否则没有相干，自己删自己的），而又不会出现子串的情形，所以肯定只有结论 3 的情况才会出现 Yes 的可能性。
下面就是需要判断 $S_i$ 的后缀和某个 $S_j$ 的前缀匹配，并且 $S_i, S_j$ 的剩余部分不同。有接着使用 AC 自动机做法，但人懒了，直接大力 Hash 做。
具体的，可以考虑枚举每一个后缀，将其 Hash 值和剩余部分的 Hash 值存下来，然后再枚举每个前缀，尝试匹配一些后缀。时间复杂度 $O(\sum |S|)$ 或 $O(\sum |S|\log \sum |S|)$。
最后一个问题就是众所周知的 Hash 冲突问题。其实一般想卡 Hash 是比较难的，因为 Hash 自选模数，自选 base，很不好卡，不同的字符串相当于是随机数对撞。注意到如果选取模数为 $P$ 的话，那么存的个数不能超过 $O(\sqrt P)$ 个，反过来，如果我们存了 $\sum |S|$ 个数，为了使不同的字符串分开，我们至少需要 $O((\sum|S|) ^ 2)$ 的 $P$，在本题中是 $10 ^ {13}$，所以一般的模数例如 998244353，$10 ^ 9 + 7$ 之类的会 WA 一些点。
写起来还是有亿点点难写，注意由于没有多测，不要看到过了一些点就觉得自己只是 corner case 没考虑到。WA 了 16 发才过……
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
| const int N = 2e6 + 10;
const LL Mod = LL(1e15) + 37;
struct Node {
int ch[4], fa;
} tr[N];
int n, tot, len[N], edid[N];
LL pw[N], hash[N];
bool hav[N];
std::string s[N];
std::map<LL, std::vector<PII>> mp[N];
template <class T>
inline bool chkmax(T &x, T y) { return x < y ? x = y, 1 : 0; }
void insert(const char *s, int id)
{
int u = 0;
for (int i = 0, c; s[i]; ++ i)
{
if (!tr[u].ch[c = s[i] - 'A'])
len[tr[u].ch[c] = ++ tot] = i + 1;
u = tr[u].ch[c];
}
edid[u] = id;
}
void build()
{
std::queue<int> q;
for (int i = 0; i < 4; ++ i)
if (tr[0].ch[i]) q.push(tr[0].ch[i]);
while (!q.empty())
{
int x = q.front();
q.pop();
chkmax(edid[x], edid[tr[x].fa]);
for (int i = 0; i < 4; ++ i)
if (!tr[x].ch[i]) tr[x].ch[i] = tr[tr[x].fa].ch[i];
else tr[tr[x].ch[i]].fa = tr[tr[x].fa].ch[i], q.push(tr[x].ch[i]);
}
}
void fail() { std::cout << "Yes\n", exit(0); }
void init()
{
pw[0] = 1;
for (int i = 1; i < N; ++ i) pw[i] = pw[i - 1] * 5 % Mod;
}
LL gethash(int l, int r)
{
if (l > r) return 0;
return ((r < 0 ? 0 : hash[r]) + (s128) (Mod - pw[r - l + 1]) * (l == 0 ? 0 : hash[l - 1])) % Mod;
}
void inithash(std::string s)
{
hash[0] = s[0] - 'A' + 1;
for (int i = 1; s[i]; ++ i) hash[i] = (hash[i - 1] * 5LL + s[i] - 'A' + 1) % Mod;
hash[s.size()] = 0;
}
signed main()
{
init(), std::cin.tie(0)->sync_with_stdio(false);
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> s[i];
for (int i = 1; i <= n; ++ i) insert(s[i].c_str(), i);
build();
for (int id = 1; id <= n; ++ id)
{
static int stk[N];
int top = 0, bac = 0;
for (int i = 0, u = 0, c, mat; s[id][i]; ++ i)
{
c = s[id][i] - 'A', u = tr[u].ch[c];
stk[++ top] = u, mat = edid[u];
if (mat == id) mat = edid[tr[u].fa];
if (mat) bac = 1, u = stk[top -= s[mat].size()];
}
if (!top) continue;
if (bac) fail();
hav[id] = true, inithash(s[id]);
for (int i = 0; i < (int) s[id].size(); ++ i)
mp[s[id].size() - i][gethash(i, s[id].size() - 1)].push_back({gethash(0, i - 1), i});
}
for (int id = 1; id <= n; ++ id)
{
if (!hav[id]) continue;
inithash(s[id]);
for (int i = 1; i <= (int) s[id].size(); ++ i)
{
if (!mp[i].count(gethash(0, i - 1))) continue;
bool flag = true;
LL curhash = gethash(i, (int) s[id].size() - 1);
int curlen = s[id].size() - i;
for (auto [nxthash, nxtlen] : mp[i][gethash(0, i - 1)])
if (curhash != nxthash || nxtlen != curlen) flag = false;
if (!flag) fail();
}
}
std::cout << "No\n";
return 0;
}
|