用c++代码实现算法最长公共子序列相似度

以下是用C++实现最长公共子序列相似度算法的示例代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];

int main()
{
    string a, b;
    cin >> a >> b;

    n = a.size(), m = b.size();

    memset(f, 0, sizeof f);

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

    double sim = (double)f[n][m] / max(n, m);
    printf("%.2lf%%\n", sim * 100);

    return 0;
}

算法思路：

1. 定义 $f[i][j]$ 表示 $a$ 的前 $i$ 个字符和 $b$ 的前 $j$ 个字符的最长公共子序列的长度。

2. 状态转移方程：

$$
f[i][j] = \begin{cases}
max(f[i-1][j], f[i][j-1]), & a[i-1] \neq b[j-1] \\
max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1), & a[i-1] = b[j-1]
\end{cases}
$$

3. 最长公共子序列相似度为最长公共子序列长度除以 $a$ 和 $b$ 中的最大长度。

4. 时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。