Statement
给两个串 \(A,B\),其中 \(|A|,|B|\le2000\),计算:
- \(A\) 的最短子串,他不是 \(B\) 的子串
- \(A\) 的最短子串,他不是 \(B\) 的子序列
- \(A\) 的最短子序列,他不是 \(B\) 的子串
- \(A\) 的最短子序列,他不是 \(B\) 的子序列
Solution
子序列自动机:\(\delta(u,c)=\min\{i|i>u\land s_i=c\}\),可 \(O(n|\Sigma|)\) 求出
那么这四问都可以转化成:有两个 DAG 记为 \(A,B\),起始点都为 \(0\),求最短的路径使 \(A\) 能完整走完,而 \(B\) 不能。
设 \(f(i,j)\) 为 \(A\) 上从 \(i\) 出发,\(B\) 上从 \(j\) 出发的最短路径长度,有
\[ f(i,j)=\min_{c\in\Sigma}\{f(\delta_A(i,c),f(\delta_B(j,c)))+1\} \]边界:对于 \(i,j\),若存在 \(c\),存在转移 \(\delta_A(i,c)\) 且不存在转移 \(\delta_B(j,c)\),则 \(f(i,j)=0\).
答案:\(f(0,0)\)
时间:\(O(n^2|\Sigma|)\)
标签:子串,4.1,Sigma,delta,序列,H7.1 From: https://www.cnblogs.com/laijinyi/p/18425918