TB椰程 TypeBuddy 打字搭子

最长公共子序列

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 653 字

f[i][j] 两前缀 LCS，相等+1否则取大

  • 动态规划
  • 最长公共子序列

前置内容

正文

// LCS：最长公共子序列
// 两串都不必连续
// DP：f[i][j] 两前缀 LCS
// 字符相等 +1，否则取大
#include <cstdio>
#include <cstring>
char a[1005], b[1005];
int f[1005][1005], la, lb;
int main() {
    scanf("%s%s", a, b);
    la = strlen(a);
    lb = strlen(b);
    // 空串 LCS 为 0，已自然初值
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++)
            // 当前字符相等
            if (a[i - 1] == b[j - 1])
                f[i][j] = f[i - 1][j - 1]
                    + 1;
            // 否则继承较大前缀
            else f[i][j] = (f[i - 1][j]
                > f[i][j - 1])
                ? f[i - 1][j]
                : f[i][j - 1];
    printf("%d", f[la][lb]);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK