2022ICPC亚洲网络选拔赛L.LCS-like Problem（DP + 字符串）

可以在PTA补题。

题目大意 / Problem

给定两个字符串s和t，求一个s的子串s'使得s'和t的最大公共子串长度不超过1，问s'的最大长度。

子串可以不连续。

思路 / Thought

先把字符转换成[0, 25]的数字方便处理。

根据题意判断应该是个DP。由于是一个和位置和字符有关的dp，状态可以设为\(dp[i][j]\)，表示到s的第i个位置为止，最后一个敏感字符（定义为存在于t中的字符）为j的最大合法s'长度。

还需要预先处理一个ban数组，ban[i][j]表示在s'中字符i后面不能接j，这样会导致s'与t的公共子串有至少两个字符相同。这个数组需要从后往前处理，记录一下哪些字符在从后往前的过程中已经出现，并且记录下来更新ban数组。

从前往后遍历s数组，到第i位时有两种情况，第一种是s[i]没在t中出现过，也就是这个字符加入到s'中不会对公共子串长度造成影响。第二种情况是s[i]在t中出现过，就只有ban[j][s[i]]为假的情况才能将状态dp[i - 1][j]转移到dp[i][s[i]]。

在转移时，前一个状态为：到s的i - 1位为止，以j作为敏感字符结尾的字符串最大长度。

当前状态为到s的i位为止，以j或s[i]作为敏感字符结尾的字符串最大长度。

最后只需要输出dp[n][i]（0 <= i < 26）的最大值就好了。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 9;
int n, m;
bitset<30> vis, ban[30];//vis[i]表示i在t中出现过，标记为敏感字符 
int dp[maxn][30];
char s[maxn], t[maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> s + 1;
	cin >> t + 1;
	n = strlen(s + 1), m = strlen(t + 1);
	for(int i = 1;i <= n; ++ i)s[i] -= 'a';
	for(int i = 1;i <= m; ++ i)t[i] -= 'a';
	
	for(int i = m;i >= 1; -- i)
	{
		for(int j = 0;j < 26; ++ j)if(vis[j])ban[t[i]][j] = true;
		vis[t[i]] = true;
	}
	
	for(int i = 1;i <= n; ++ i)
	{
		for(int j = 0;j < 26; ++ j)
		{
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);//延续性 
			
			if(!vis[s[i]])//从j转移过来敏感字符依然是j
				dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);
			else if(!ban[j][s[i]])//敏感字符是s[i] 
				dp[i][s[i]] = max(dp[i][s[i]], dp[i - 1][j] + 1);	 
		}
	}
	
	int ans = 0;
	for(int i = 0;i < 26; ++ i)ans = max(ans, dp[n][i]);
	cout << ans << '\n';
	
	return 0;
}