【算法漫笔003】KMP自动机+DP

FeIndentOvO

2026-08-21 09:51:14

发布于：重庆

23阅读

0回复

0点赞

【算法漫笔003】浅谈KMP自动机+DP

普通的 KMP 显然无法嵌套入 DP 当中。尽管普通 KMP 的时间复杂度均摊为 $O(N)$ （下文中所有 $N$ 表示文本长度， $M$ 表示模式串长度， $R$ 表示字符集大小），但普通 KMP 的 while 回退只有在单条路径连续执行时才能均摊 $O(1)$ ，如果想要嵌套进 DP 里面，由于 DP 是多条路径并行枚举，均摊失效，时间复杂度可能来到 $O(L \times M^2 \times R)$ 。于是便有了 KMP自动机。

KMP自动机的原理

KMP 自动机的原理实际上和普通 KMP 相同，唯一的区别是在回退指针时，普通 KMP 使用一维的 $next$ 数组在匹配过程中动态计算并回退位置，while 执行 j=next[j-1]。

而 KMP 自动机则牺牲了一些空间复杂度，它将 $next$ 数组升级成二维，把所有可能的回退路径提前预处理，构建成二维的 $next_{i,j}$ ，表示已匹配长度为 j，读入字符 c 后的一步直达的最新状态。

显然两者在单次匹配的时间复杂度相同，但 KMP 自动机的空间复杂度比普通 KMP 花销更大，看起来似乎 KMP 自动机没有任何用处、可以被 KMP 取代，但事实真的如此吗？

KMP自动机+DP

原题链接：https://www.luogu.com.cn/problem/P3082

我们来看这样一道题，简化题意，即从 $S$ 中选择一个最长的子序列，使得该序列不包含 $T$ 这个连续子串，子序列的长度最长为多少。 $T_{len} \le S_{len} \le 10^4$

容易想到 $DP$ 。我们设 $dp_{i,j}$ 表示处理完 $S$ 的前 $i$ 个字符后，当前选择的子序列与模式串 $T$ 的最长可匹配前缀长度为 $j$ 时，能够保留的最大字符数。

思考转移。

删除 $S_i$ 的状态很容易，即状态不变，保留数也不变，则 $dp_{i+1,j}=\max(dp_{i+1,j},dp_{i,j})$

保留 $S_i$ 则需用到 KMP 自动机。查自动机转移表 $next_{j,S_i}$ 即可得到新状态 $j'$ 。

此时若 $j'=M$ ，说明拼接后出现了子串 $T$ ，转移非法，跳过。

否则可以直接进行转移，显然 $dp_{i+1,j'}=\max(dp_{i+1,j'},dp_{i,j}+1)$

显然，初始化 $dp_{0,0}=0$ ，其它为 $-INF$ ，答案即为 $\max(dp_{n,j})(0 \le j \le M)$ 。

但是我们能够发现，这个大小的数组显然会让我们陷入 MLE 的恐慌当中，此时我们只需要滚动数组即可。

这样你就成功的水过了一道青题。

/*
Becoder c2028hf2
Luogu FeIndent
ACGO FeIndentOvO
*/
#include<bits/stdc++.h>
#define int long long
#define fast_IO ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr)
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e3+5;
const int W=26;
string s,t;
int dp[N],n,m,pi[N],next_[N][W],ans=-INF;
void init() {
	for (int i=1;i<m;i++) {
		int j=pi[i-1];
		while (j>0&&t[i]!=t[j]) {
			j=pi[j-1];
		}
		if (t[i]==t[j]) {
			j++;
		}
		pi[i]=j;
	}
	for (int j=0;j<=m;j++) {
		for (int c=0;c<W;c++) {
			if (j<m&&c==t[j]-'a') {
				next_[j][c]=j+1;
			}
			else if (j==0) {
				next_[j][c]=0;
			}
			else {
				next_[j][c]=next_[pi[j-1]][c];
			}
		}
	}
}
signed main() {
	fast_IO;
	cin >> s >> t;
	n=s.size(),m=t.size();
	init();
    memset(dp,-INF,sizeof dp);
    dp[0]=0;
	for (int i=0;i<n;i++) {
		int dp2[N];
		memset(dp2,-INF,sizeof dp);
		for (int j=0;j<m;j++) {
			if (dp[j]<=-INF) {
				continue;
			}
			dp2[j]=max(dp2[j],dp[j]);
			if (next_[j][s[i]-'a']<m) {
				dp2[next_[j][s[i]-'a']]=max(dp2[next_[j][s[i]-'a']],dp[j]+1);
			}
		}
		memcpy(dp,dp2,sizeof dp);
	}
	for (int j=0;j<m;j++) {
		ans=max(ans,dp[j]);
	}
	cout << n-ans;
	return 0;
}