11056번: 두 부분 문자열

https://www.acmicpc.net/problem/11056

$O(l_al_b)$

답은 (a 길이) + (b 길이) - (LCA(a,b) 길이)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[1002], b[1002];
int dp[1001][1001], n, m;
int main() {
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    for (int i = 1; a[i]; i++)
        for (int j = 1; b[j]; j++)
            dp[i][j] = max({ dp[i - 1][j - 1] + (a[i] == b[j]),dp[i - 1][j],dp[i][j - 1] });
    printf("%d", n + m - dp[n][m]);
    return 0;
}