Longest Common Substring

최장 부분 공통 문자열

두 문자속에 공통으로 포함되어있는 연속적인 문자열의 최대 길이를 찾는 알고리즘이다.

C++

int LCSubstring(string a, string b){
    int n = a.size();
    int m = b.size();
    a = ' ' + a;
    b = ' ' + b;
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i] == b[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    return ans;
}