1958번: LCS 3

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


$O(lmn)$

2차원 lcs dp를 응용한다.

#include<cstdio>
#include<algorithm>
char s1[102], s2[102], s3[102];
int dp[101][101][101], i, j, k;
int main() {
    scanf("%s %s %s", s1 + 1, s2 + 1, s3 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            for (k = 1; s3[k]; k++)
                dp[i][j][k] = std::max({ dp[i - 1][j - 1][k - 1] + (s1[i] == s2[j] && s1[i] == s3[k]),dp[i - 1][j][k],dp[i][j - 1][k],dp[i][j][k - 1] });
    printf("%d", dp[i - 1][j - 1][k - 1]);
    return 0;
}