题目描述
https://codeforces.com/gym/103388/problem/B
简要题意：给定一个长度为 $n$ 的模板串 $S$ 和 $m$ 个查询串 $T_i$，现在对 $S$ 做 $m$ 次循环左移，令 $Q_i$ 表示第 $i$ 次循环左移的结果，$Q_i=S_iS_{i+1}\cdots S_nS_1S_2\cdots S_{i-2}S_{i-1}$，同时令 $Q_i$ 的贡献为 $Q_i$ 的长度最长的一个子串的长度，满足这个子串也是某个 $T_i$ 的子串，现在要求所有 $Q_i$ 的贡献的最小值
$n,m,|S|,\sum |T_i|\le 10^5$
Solution
我们考虑首先将 $S$ 复制一遍，这样以 $S_i$ 开始的长度为 $n$ 的子串就是 $Q_i$，然后我们对所有 $T$ 建广义后缀自动机，这样我们可以在枚举 $S$ 前缀的同时得到当前前缀的最长后缀，满足这个后缀是某个 $T$ 的子串
我们考虑二分答案，那么对于每个枚举出的前缀的后缀，我们发现满足答案的 $Q_i$ 的 $i$ 是一个区间，那么我们直接做一个区间覆盖即可判断，这里的所有区间覆盖可以直接通过差分来做
时间复杂度 $O(n\log n)$
```cpp
include
include
include
include
include
include
include
define maxn 100010
define Maxn 200010
define lowbit(i) ((i) & (-i))
define ll long long
using namespace std;
int n, m, a[maxn 2];
char s[maxn], t[maxn 2];
struct SAM {
int cnt, L, l, nxt[26];
} T[Maxn]; int f[Maxn], top, last, rt;
void init_SAM() {
for (int i = 1; i <= top; ++i) {
T[i].cnt = T[i].L = T[i].l = f[i] = 0;
fill(T[i].nxt, T[i].nxt + 26, 0);
}
rt = last = top = 1;
T[rt].L = T[rt].l = f[rt] = 0;
}
int extend(int p, int ch) {
if (T[p].nxt[ch]) {
int q = T[p].nxt[ch], nq;
if (T[q].L - 1 == T[p].L) return q;
nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
memcpy(T[nq].nxt, T[q].nxt, sizeof T[q].nxt);
while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
f[q] = nq; return nq;
}
int np = ++top; T[np].L = T[p].L + 1;
while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
if (!p) return (f[np] = rt, np);
int q = T[p].nxt[ch];
if (T[q].L - 1 == T[p].L) f[np] = q;
else {
int nq = ++top; T[nq].L = T[p].L + 1;
f[nq] = f[q]; memcpy(T[nq].nxt, T[q].nxt, sizeof T[q].nxt);
while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
f[np] = f[q] = nq;
}
return np;
}
void insert(char *s) {
int l = strlen(s), p = rt;
for (int i = 0; i < l; ++i) p = extend(p, s[i] - ‘a’);
}
int d[maxn];
bool check(int x) {
for (int i = 1; i <= n; ++i) d[i] = 0;
for (int i = 1; i < 2 * n; ++i) {
if (a[i] < x) continue; int l = i - a[i] + 1, r = i;
int L = max(1, l + x - 1 - n + 1), R = min(n, r - x + 1);
++d[L]; —d[R + 1];
} int s = 0;
for (int i = 1; i <= n; ++i) d[i] += d[i - 1], s += d[i] > 0;
return s == n;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> t + 1; init_SAM();
for (int i = 1; i <= m; ++i) cin >> s, insert(s);
for (int i = n + 1; i < 2 * n; ++i) t[i] = t[i - n];
int p = rt, len = 0;
for (int i = 1; i < 2 * n; ++i) {
int ch = t[i] - 'a';
if (T[p].nxt[ch]) p = T[p].nxt[ch], ++len;
else {
while (p && !T[p].nxt[ch]) p = f[p];
if (!p) p = rt, len = 0;
else len = T[p].L + 1, p = T[p].nxt[ch];
} a[i] = min(len, n);
}
int l = 0, r = n, mid, ans;
while (l <= r) {
mid = l + r >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
} cout << ans << "\n";
return 0;
}