还想用hash记录……果然是天真。lcs转移比较简单,每次增加1。每次找是当前-1的就行了。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int mod = ;
const int maxn = ;
char a[maxn];
char b[maxn];
int dp[maxn][maxn];
int fa[mod];
int na, nb; int main() {
// freopen("in", "r", stdin);
while(~scanf("%s %s", a, b)) {
memset(dp, , sizeof(dp));
memset(fa, -, sizeof(fa));
na = strlen(a);
nb = strlen(b);
for(int i = ; i < na; i++) {
for(int j = ; j < nb; j++) {
if(a[i] == b[j]) {
if(dp[i][j] + > max(dp[i][j+], dp[i+][j])) {
dp[i+][j+] = dp[i][j] + ;
// int cur = (((i + 1) * 59) % mod + ((j + 1) * 61) % mod) % mod;
// int pre = ((i * 59) % mod + (j * 61) % mod) % mod;
// fa[cur][0] = pre;
// fa[cur][1] = i;
// ii = cur;
}
else dp[i+][j+] = max(dp[i][j+], dp[i+][j]);
}
else {
dp[i+][j+] = max(dp[i][j+], dp[i+][j]);
}
}
}
int ii = na;
int jj = nb;
char st[maxn];
int top = ;
while(dp[ii][jj]) {
if(dp[ii][jj] == dp[ii-][jj]) ii--;
else if(dp[ii][jj] == dp[ii][jj-]) jj--;
else {
ii--, jj--;
st[top++] = a[ii];
} }
while(top) printf("%c", st[--top]);
printf("\n");
}
return ;
}