可以在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; }
Comments NOTHING