基因序列相似性问题

考虑一下最长公共子序列的求法：

dp[i][j]=\max\left\{ \begin{aligned} &dp[i-1][j-1](a[i]==b[j])\\&dp[i][j-1]\\&dp[i-1][j] \end{aligned} \right.

我们可以加一位 $k$ ，表示 $kmp$ 匹配到了哪一位。

我们可以这么理解，执行求 $next[]$ 后，运行 $Insert(ch,j)$ （ $j$ 是上一次匹配到的位置），当 $ch,j$ ，返回值肯定是固定的，表示这一次匹配到的位置，于是列出 $dp[i+1][j+1][Insert(A[i+1],k)]=dp[i][j][k]+1)$ 的 $dp$ 方程。

inline int Insert(char ch,int j){
	while (j&&ch!=P[j+1]) j=nex[j];
	if (ch==P[j+1]) j++;
	return j;
}

代码：

#include <bits/stdc++.h>
#define MAXN 205
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
char A[MAXN],B[MAXN],P[MAXN];
int nex[MAXN],dp[MAXN][MAXN][MAXN];
int n,m,p;
inline void Build(){
	int j=0;
	for (register int i=2;i<=p;++i){
		while (j&&P[i]!=P[j+1]) j=nex[j];
		if (P[i]==P[j+1]) j++;
		nex[i]=j;
	}
}
inline int Insert(char ch,int j){
	while (j&&ch!=P[j+1]) j=nex[j];
	if (ch==P[j+1]) j++;
	return j;
}
inline void chkmax(int &a,int b){
	if (b>a) a=b;
}
int main(){
	m=read(),n=read(),p=read();
	scanf("%s",A+1);
	scanf("%s",B+1);
	scanf("%s",P+1);
	Build();
	for (register int i=0;i<=m;++i){
		for (register int j=0;j<=n;++j){
			for (register int k=0;k<p;++k){
				if (i+1<=m&&j+1<=n&&A[i+1]==B[j+1]){
					chkmax(dp[i+1][j+1][Insert(A[i+1],k)],dp[i][j][k]+1);
				}
				chkmax(dp[i+1][j][k],dp[i][j][k]);
				chkmax(dp[i][j+1][k],dp[i][j][k]);
			}
		}
	}
	int ans=0;
	for (register int i=0;i<p;++i){
		ans=max(ans,dp[m][n][i]);
	}
	printf("%d\n",ans);
}