5582번: 공통 부분 문자열

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


$O(l^2)$

dp[i][j]: s1은 i번째 s2는 j번째를 끝으로 하는 최대 공통 문자열 길이
dp[i][j]= s1[i]==s2[j] 라면 dp[i-1][j-1]+1 아니면 0

#include<cstdio>
char s1[4002], s2[4002];
int dp[4001][4001], r;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (int i = 1; s1[i]; i++) {
        for (int j = 1; s2[j]; j++) if (s1[i] == s2[j]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if (dp[i][j] > r) r = dp[i][j];
        }
    }
    printf("%d", r);
    return 0;
}