壹、题目描述 ¶
贰、题解 ¶
本文其实是思考过程，思路可能稍显混乱。
能够想到对标准串建广义 \(\rm SAM\)，显然能对 \(l\) 进行二分，那么我们现在考察的就是，对于一个 \(l\)，如何校验其正确性？或者说，存在怎样的最优分割能让我们分割出来的串尽可能进行匹配？
确实不难想到 \(\rm DP\)，考虑有用的信息：
- 当前位；
- 从当前开始，已经匹配的最长长度；
- 当前位置在 \(\rm SAM\) 上的匹配点；
- 当前已经得到的合法匹配串的长度；
状态将所有信息存下固然是可行的，但肯定是不行的（？）。
考察一个错误的贪心 —— 贪心地匹配尽可能长的长度。但是由于可能可以将前面的某些匹配串的字符让到后面，使得后面的串也能够变得合法，这样的贪心显然不正确。
不妨找到每个右端点能匹配的最多的左端点，这个在 \(\rm SAM\) 上能够做到，现在问题变成了，从这些区间中，选出一些不相交的区间，每个区间都能够被一个大区间包含，是否能让这些区间覆盖超过 \(90\%\) 的点。
还是不行，但是注意到我们并不要求具体地分割方案，有没有什么更不用在意具体分割方案的转化吗？
重拾 \(\rm DP\)，定义状态 \(f(i)\) 表示最后一个单词到 \(i\) 结尾，能够匹配的最长长度，那么我们枚举前一个分割点 \(j\in [1,i)\)，将 \((j,i]\) 的词进行匹配即可。
不过需要注意的是，可能有空挡，所以还要 \(f(i)\) 和 \(f(i-1)\) 取 \(\max\) 才行（注意 \(\rm DP\) 含义的微小变化）。
不难发现这个 \(\rm DP\) 的复杂度事实上是 \(\mathcal O(n^3)\) 的，我们可以进行一些优化。
设 \(L(i)\) 表示以 \(i\) 结尾，最长的匹配单词的左端点在 \(L(i)\)，那么，我们枚举 \(j\) 的时候，就可以这样：
- 对于 \(j<L(i)\)，有 \(f(i)=\max f(j)+i-L(i)+1\)；
- 对于 \(j\ge L(i)\)，有 \(f(i)=\max f(j)+i-j\)；
我们将两个转移综合一下，有
\[f(i)=\max \left\{f(j)-\max\{L(i)-1,j\} \right\} \]线段树优化，复杂度变成 \(\mathcal O(n\log^2 n)\). 好像还是不行。还有什么性质啊？
嘿，其实刚刚的 \(f(i-1)\) 取 \(\max\) 就可以包含空挡，并且 \(j<L(i)\) 的转移部分其实也是空挡，我们只需要和 \(f(i-1)\) 取 \(\max\) 就可以代替这部分的转移了，那么，我们的转移变成了：
\[f(i)=\max\{f(j)+i-(j+1)+1,f(i-1)|j \in[L(i)-1,i-l]\} \]之后，方程变成了
\[f(i)=\max\{f(j)-j+i,f(i-1)|j \in[L(i)-1,i-l]\} \]维护一个 \(f(j)-j\) 的单减队列就行了。复杂度就变成了 \(\mathcal O(n\log n)\) 了。别忘了算上二分的复杂度。这算黑题？
叁、参考代码 ¶
const int maxn=2.2e6; // twice
const int sigma=2;
int trie[maxn+5][sigma], fa[maxn+5];
int len[maxn+5], ncnt=1, lst;
inline void add(int c){
int p=lst, u, q, nq;
if(trie[p][c]){
q=trie[p][c];
if(len[q]==len[p]+1) lst=q;
else{
nq=lst=++ncnt;
for(int i=0; i<sigma; ++i)
trie[nq][i]=trie[q][i];
fa[nq]=fa[q], len[nq]=len[p]+1;
fa[q]=nq;
for(; p && trie[p][c]==q; p=fa[p])
trie[p][c]=nq;
}
return;
}
u=lst=++ncnt;
len[u]=len[p]+1;
for(; p && !trie[p][c]; p=fa[p])
trie[p][c]=u;
if(!p) fa[u]=1;
else{
q=trie[p][c];
if(len[q]==len[p]+1) fa[u]=q;
else{
nq=++ncnt;
for(int i=0; i<sigma; ++i)
trie[nq][i]=trie[q][i];
fa[nq]=fa[q], len[nq]=len[p]+1;
fa[q]=fa[u]=nq;
for(; p && trie[p][c]==q; p=fa[p])
trie[p][c]=nq;
}
}
}
int T, n, m;
char s[maxn+5];
inline void input(){
T=readin(1), m=readin(1);
rep(t, 1, m){
lst=1; scanf("%s", s+1);
n=strlen(s+1);
rep(i, 1, n) add(s[i]-'0');
}
}
int L[maxn+5];
inline void getL(){
int u=1, cur_len=0;
for(int i=1; i<=n; ++i){
int to=s[i]-'0';
while(u && !trie[u][to])
u=fa[u], cur_len=min(cur_len, len[u]);
if(!u) u=1, cur_len=0;
else u=trie[u][to], ++cur_len;
L[i]=i-cur_len+1;
}
// rep(i, 1, n) printf("L[%d] == %d\n", i, L[i]);
}
int f[maxn+5], Q[maxn+5], op, ed;
inline bool check(int l){
op=1, ed=0;
rep(i, 0, l-1) f[i]=0;
rep(i, l, n){
f[i]=f[i-1];
while(op<=ed && f[Q[ed]]-Q[ed]<f[i-l]-(i-l)) --ed;
Q[++ed]=i-l;
while(op<=ed && Q[op]<L[i]-1) ++op;
if(op<=ed) f[i]=max(f[i], f[Q[op]]-Q[op]+i);
}
return f[n]*10>=n*9;
}
inline int bisearch(){
int l=0, r=n, mid, ret=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) ret=mid, l=mid+1;
else r=mid-1;
}
return ret;
}
signed main(){
input();
while(T--){
scanf("%s", s+1);
n=strlen(s+1);
getL();
int ans=bisearch();
writc(ans);
}
return 0;
}
肆、关键之处 ¶
类似 \(f(i)=\max\{f(j)-j+i,f(i-1)|j \in[L(i)-1,i-l]\}\)，后面的区间左端点满足单调不减的，可以考虑维护单调队列。
单调队列其本质上还是一个最优解覆盖问题，如果解越后面，并且值又很大，那么又排在前面，值又比它小的点就没有必要存在了。
该题在 Luogu 上为黑，但个人赶脚评分虚高，只是知识点稍显高级，但算法上并没有有机结合，更像是拼盘题......大概 蓝+ 差不多？