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\)的后面出現來輔助轉移就可以完成，
? https://blog.csdn.net/Berserker____/article/details/109062238
#include <bits/stdc++.h>
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 <= n; i ++) s[i] -= 'a';
for(int i = 1; i <= m; i ++) t[i] -= 'a';
init();
for(int i = 1; i <= n; i ++)
{
for(int j = 0; j < 26; j ++)
f[i][j] = f[i - 1][j] + (vis[s[i]] == 0); //如果s[i]沒有在t中出現，可以直接接在后面，且不影響末尾
for(int j = 0; j < 26; j ++)
if(!ban[j][s[i]] && vis[s[i]]) //如果存在這個數，那么不能接在j的后面
f[i][s[i]] = max(f[i][s[i]], f[i - 1][j] + 1);
}
int res = 0;
for(int i = 0; i < 26; i ++)
res = max(res, f[n][i]);
cout << res << '\n';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509041.html
標籤：其他
上一篇：隱馬爾科夫模型的簡單實作