题目描述

blablabla

样例

blablabla

算法1

(暴力枚举)$

最长串不是难题
f[i][j] 到a的前i个字符, b的前j个字符的最长串长度
f[i][j] = f[i - 1][j - 1] + (a[i] == a[j]);
f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]));

主要是回溯问题, 写了个简单的的dfs, 超时了
然后优化用set存状态,还是超时,首先看一下dfs状态
dfs(int x, int y, int k) 在a的前x个字符,b的前y个字符找第k个字符
我们发现
当选择的字符一样时, 选择字符的位置越靠近x,y越优,
可以包含后面同样时相同字符时的情况,
所以直接找距离 x 和 y 最近的字符a的位置即可;

那就再弄个数组 fa[i][j] 表示a字符串前i个字符中字母j + ‘a’最近出现的位置
if (a[i] - ‘a’ == j) fa[i][j] = i;
else fa[i][j] = f[i - 1][j];

fb[i][j] 同理

复杂度最坏的话应该是 O(26 * lena + 26 * lenb + lena * lenb + min(lena, lenb) * 26 * 2)
(也有可能都算错了,瞎算的)

直接用set剪枝爆搜也是能过的

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;

const int maxn = 81;

char a[maxn], b[maxn], ans[maxn];
int f[maxn][maxn], fa[maxn][26], fb[maxn][26];
vector<string> ve;

void dfs(int x, int y, int k)
{
    if (k == 0) { ve.pb(string(ans + 1)); return; }
    for (int i = 0; i < 26; ++i)
    {
        int a = fa[x][i], b = fb[y][i];
        if (a < k || b < k || f[a][b] != k) continue;
        ans[k] = 'a' + i;
        dfs(a - 1, b - 1, k - 1);
    }
}

int main()
{
    cin >> a + 1 >> b + 1;
    int lena = 1, lenb = 1; 

    for (int& i = lena; a[i]; ++i)
        for (int j = 0; j < 26; ++j) 
            if (a[i] - 'a' == j) fa[i][j] = i;
            else fa[i][j] = fa[i - 1][j];

    for (int& i = lenb; b[i]; ++i)
        for (int j = 0; j < 26; ++j)
            if (b[i] - 'a' == j) fb[i][j] = i;
            else fb[i][j] = fb[i - 1][j];

    for (int i = 1; a[i]; ++i)
        for (int j = 1; b[j]; ++j)
        {
            f[i][j] = f[i - 1][j - 1] + (a[i] == b[j]);
            f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]));
        }

    dfs(lena - 1, lenb - 1, f[lena - 1][lenb - 1]);

    sort(ve.begin(), ve.end());
    for (string i : ve) cout << i << '\n';
    return 0;
}