本文共 3996 字，大约阅读时间需要 13 分钟。

题目

题目描述

1. 非 $B$ 子串的 $A$ 的子串
2. 非 $B$ 子序列的 $A$ 的子串
3. 非 $B$ 子串的 $A$ 的子序列
4. 非 $B$ 子序列 $A$ 的子序列

数据范围与提示

思路

$\mathtt{P}\mathtt{A}\mathtt{R}\mathtt{T}1$

一种做法是，二分答案，把 $|A|$ 个该长度的子串取出来（利用哈希），然后在 $B$ 里查是否存在。复杂度 $\mathcal{O}(n{\log }^{2}n)$ 。（可行性源于，若长度为 $L$ 的 $A$ 的子串已经不存在，那么 $L+1$ 长度必然也不存在。）

还有另一种做法，就是利用 $\mathtt{S}\mathtt{A}\mathtt{M}$ 去掉不可行的子串。或许好打一点。

忽然想到第三种，最简单的暴力做法：把 $A$ 的所有子串拿去做匹配……

$\mathtt{P}\mathtt{A}\mathtt{R}\mathtt{T}2$

只要选择的是 $A$ 的子串都很好办——数量很有限。考虑用类似 $\mathtt{d}\mathtt{p}$ 的方式优化枚举就行。

$f(l,r)$ 表示 $A$ 从 $l$ 到 $r$ 的子串，要匹配到 $B$ 的哪个前缀的子序列才行。在 $B$ 尾端加入无穷多个通配符。那么有转移

$$f(l,r)=\underset{t>f(l,r-1)}{\overset{B_t=A_r}{\min }}t$$

显然 $f(l,r)$ 在 $l$ 这一维上单调不增。先枚举 $r$ ，而后从小到大枚举 $l$ ，就可实现 $\mathcal{O}(1)$ 转移。

$\mathtt{P}\mathtt{A}\mathtt{R}\mathtt{T}3$

感觉更棘手了。因为序列我们维护不了。我们只会子串。咋整？将计就计，对 $B$ 建立 $\mathtt{S}\mathtt{A}\mathtt{M}$ 即可。

想一个暴力做法：把 $A$ 的每个子序列拿去试着匹配 $B$ 的子串。若是已经无法匹配了，那么最好就是以此处为结束点。所以，只有可匹配的才有价值。那么 $\mathtt{S}\mathtt{A}\mathtt{M}$ 上每个点维护，匹配到此处的最短子序列。

转移的时候，对于一个 “可匹配” 的 $y$ ，如果其 $A_{x+1}$ 儿子为空，那么 $le{n}_y+1$ 为可行答案；否则打上可匹配 $le{n}_y+1$ 标记。这里的 $len$ 是指最短可匹配长度。

复杂度 $\mathcal{O}(n^2)$ ，和 $\mathtt{P}\mathtt{A}\mathtt{R}\mathtt{T}2$ 一样慢得很。

$\mathtt{P}\mathtt{A}\mathtt{R}\mathtt{T}4$

完了！我们根本不会处理子序列！我们只会 $\mathtt{S}\mathtt{A}\mathtt{M}$ ！天崩地裂，丘峦崩摧！

所以抛开自动机，直接 $\mathtt{d}\mathtt{p}$ 好了。用 $f(x,y)$ 表示，$A$ 的前 $x$ 个字符中，有一个长度为 $y$ 的子序列，使得 $B$ 必须用前 $f(x,y)$ 个字符才能完成匹配。（匹配的思想和 $\mathtt{P}\mathtt{A}\mathtt{R}\mathtt{T}3$ 一致。）

转移就是，找到最小的 $t$ 满足 $t>f(x,y)$ 且 $B_t=A_{x+1}$ 那么有

$$f(x+1,y+1)=\max [f(x,y+1),t]$$

考虑到 $f(x,y)$ 在两个维度上都递增，从小到大枚举 $x$ 后，从大到小枚举 $y$ 。这样 $t$ 的取值范围就是越来越大的，就可以实现 $\mathcal{O}(1)$ 转移了。

在 $B$ 末尾加入无穷多通配符。答案就是让 $f(x,y)$ 用到了通配符的 $\min y$ 。

总结

其实四个部分并不是非常难，但是杂糅在一起容易把人心态搞崩。如果我不用写博客的方式来推导，可能也会花费不少时间。

容易受到定式思维误导。其实 $\mathtt{S}\mathtt{A}\mathtt{M}$ 是配角；真正起决定性作用的是 $\mathtt{d}\mathtt{p}$ 。我们引入 $\mathtt{S}\mathtt{A}\mathtt{M}$ 只是为了字符串匹配而已。用自动机节点表示匹配情况是常见的 $\mathtt{d}\mathtt{p}$ 操作了；学过 $\mathcal{A}\mathcal{C}$ 自动机的童鞋肯定深有体会。

代码

我的 $\mathsf{s}\mathsf{o}\mathsf{l}\mathsf{v}\mathsf{e}1()$ 写复杂了。建议读者自行更改。

#include 
   
     #include 
    
     #include 
     
      #include 
      
       using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(int x){   	if(x > 9) writeint(x/10);	putchar((x-x/10*10)^48);}const int MaxN = 4005;const int CharSiz = 26;namespace SAM{   	int ch[MaxN][CharSiz];	int fa[MaxN], len[MaxN];	int lst = 1, cntNode = 1;	void clear(){   		memset(ch,0,MaxN*CharSiz<<2);		memset(fa,0,MaxN<<2);		memset(len,0,MaxN<<2);		lst = cntNode = 1;	}	void add(char c){   		int p = lst; // last one		int now = lst = ++ cntNode;		len[now] = len[p]+1; // pre		for(; p && !ch[p][c]; p=fa[p])			ch[p][c] = now; // new string		if(!p) return void(fa[now] = 1);		int x = ch[p][c]; // maybe parent		if(len[x] == len[p]+1)			return void(fa[now] = x);		int y = ++ cntNode; // split x		memcpy(ch[y],ch[x],CharSiz<<2);		fa[y] = fa[x], fa[x] = y; // chain		len[y] = len[p]+1, fa[now] = y;		for(; ch[p][c]==x; p=fa[p])			ch[p][c] = y; // change son	}	void build(char ppl[],int llt){   		clear(); // good habit		for(int i=0; i
       
         x) ans = x;	}	if(ans != MaxN)		printf("%d\n",ans);	else puts("-1");}void solve2(){   	int ans = MaxN;	memset(f,-1,2*MaxN<<2);	for(int r=0; r
        
          f[fr][j]+1) f[i&1][y] = f[fr][j]+1; for(int j=1; j<=cntNode; ++j){ f[i&1][j] = min(f[i&1][j],f[fr][j]); f[fr][j] = 0x3f3f3f3f; } } if(ans != MaxN) printf("%d\n",ans); else puts("-1");}void solve4(){ memset(f,-1,2*MaxN<<2); // no cost for(int i=0; i