L LCS-like Problem（DP 子序列自动机）
给出两个串s, t。请找出一个最长的子序列(s’)，使其与(t)的最长公共子序列长度不大于1。输出这个最长的长度。
题目名字是LCS，且题意比较符合DP的定义，优先考虑DP而非字符串来求解问题。
题目要求在s中找一个最长的满足题意的子序列。那么我们的状态表示一定是跟s有关的，又可以知道本题的转移一定是跟字符存在关系的。根据经验，可以定义出(f[i][j])表示在s的前i个字符中选择，且最后一个在t中出现的字符为j（这里是由后面转移时推出）的最大长度。
转移的时候，对于(s[i])的两种情况我们需要分别讨论。一：当(s[i])不在(t)中的时候，那么他可以跟在任何字符的后面。二：当(s[i])存在于(t)中的时候，我们要根据是否能接成一个长度大于1的子序列来判断是否能进行转移。
这里解答两个点，其一是对于f数组的定义。由于动态规划的无后效性，我们可以知道我们每次转移的时候只需要看最后一个字符就可以了。但是有一个问题，当最后一个字符(s[i])不在(t)的时候，如果定义为最后一个字符，就会覆盖掉上一个正在限制后面无效状态的状态。所以我们定义的是， 最后一个在t中的字符。
其二是关于序列自动机这个东西。其实这个知识点还挺复杂的，详情可以观看下方链接。不过本题主要只是运用其思想，本题自动机状态非常简化，只需要保存字符(j)是否能在字符(i)的后面出现来辅助转移就可以完成。
#include
using namespace std;
const int N = 500005;
char s[N], t[N];
int n, m;
int vis[26]; //t中是否已经含有i
int ban[26][26]; //i的后面不能出现j 因为是子序列
int f[N][26]; //从s的前i个字符选出的子序列，且最后一个在t中出现的字符为j的最大长度
void init() //子序列自动机预处理
{
for(int i = m; i >= 1; i --)
{
for(int j = 0; j < 26; j ++)
if(vis[j]) ban[t[i]][j] = 1;
vis[t[i]] = 1;
}
}
int main()
{
scanf("%s", s + 1);
scanf("%s", t + 1);
n = strlen(s + 1);
m = strlen(t + 1);
for(int i = 1; i
Original: https://www.cnblogs.com/DM11/p/16705945.html
Author: DM11
Title: 2022ICPC网络赛 L LCS-like Problem（DP 子序列自动机）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604195/
转载文章受原作者版权保护。转载请注明原作者出处！