传送门：点击打开链接
题意：告诉你A，B，C，求A和B的最长公共子序列，并且C不是最长公共子序列的子串
思路：先求C的Next数组，利用Next数组来完成状态的转移。
而且，用KMP来优化的dp，通常都是往后更新的写法。
对于打印路径，我们能用DFS来完成，这里有个我觉得很不错的写法，就是直接利用状压，来保存数字，感觉这样可以避免写一个结构体，方便的多
然后dp部分，就是在求最长公共子序列的基础上，再增加1维，来表示公共子序列最后一个字符是在C串的哪一个状态。
然后就是DFS在什么地方输出，应该在转移的路上增加了值时，说明在这个地方更新了答案，那时才输出。
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e2 + 5;
const int INF = 0x3f3f3f3f;int Next[MX];
char A[MX], B[MX], C[MX];
int dp[MX][MX][MX], pre[MX][MX][MX];
void GetNext(char S[]) {Next[0] = 0;for(int i = 1; S[i]; i++) {int j = Next[i - 1];while(j && S[i] != S[j]) j = Next[j - 1];Next[i] = S[i] == S[j] ? j + 1 : 0;}
}
int get(int i, int j, int k) {return (i << 16) + (j << 8) + k;
}
void DFS(int id) {int i = id >> 16, j = id >> 8 & 0xff, k = id & 0xff;id = pre[i][j][k];int ni = id >> 16, nj = id >> 8 & 0xff, nk = id & 0xff;if(!i && !j) return;DFS(id);if(dp[i][j][k] - dp[ni][nj][nk] == 1) printf("%c", A[ni]);
}
int main() {//FIN;scanf("%s%s%s", A, B, C);int l1 = strlen(A), l2 = strlen(B), l3 = strlen(C);GetNext(C);memset(dp, -INF, sizeof(dp));for(int i = 0; i < l1; i++) {for(int j = 0; j < l2; j++) dp[i][j][0] = 0;}for(int i = 0; i <= l1; i++) {for(int j = 0; j <= l2; j++) {for(int k = 0; k < l3; k++) {if(dp[i + 1][j][k] < dp[i][j][k]) {dp[i + 1][j][k] = dp[i][j][k];pre[i + 1][j][k] = get(i, j, k);}if(dp[i][j + 1][k] < dp[i][j][k]) { dp[i][j + 1][k] = dp[i][j][k];pre[i][j + 1][k] = get(i, j, k);}if(A[i] == B[j]) {int w = k + 1;while(w && A[i] != C[w]) w = Next[w - 1];w = A[i] == C[w] ? w + 1 : 0;if(dp[i + 1][j + 1][w] < dp[i][j][k] + 1) {dp[i + 1][j + 1][w] = dp[i][j][k] + 1;pre[i + 1][j + 1][w] = get(i, j , k);}}}}}int ans = 0, id;for(int i = 0; i < l3; i++) {if(dp[l1][l2][i] > ans) {ans = dp[l1][l2][i];id = get(l1, l2, i);}}if(!ans) printf("0\n");else DFS(id);return 0;
}