백준 5582 (공통 부분 문자열) - java

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

5582번: 공통 부분 문자열

유형 : DP

접근 

• 최장 공통 부분 수열(LCS)와 비슷한 문제이다. 하지만 LCS와의 차이점은 연속성이다. 수열이 아닌 문자열이기 때문에 다른 처리가 필요하다.
• a[i] != b[j] 인 경우에 처리를 하지 않는 것이 LCS와의 차이점이다. 애초에 값이 같지 않는 경우 연속성이 깨진 것이기 때문에 처리를 하지 않아야 한다.

전체 코드

import java.util.*;
import java.io.*;

public class Main {



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();

        int aLen = a.length;
        int bLen = b.length;

        int[][] dp = new int[aLen+1][bLen+1];
        int max = 0;
        for(int i=1;i<=aLen;i++){
            for(int j=1;j<=bLen;j++){

                if(a[i-1] == b[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }

                max = Math.max(max,dp[i][j]);
            }
        }

        System.out.println(max);

        br.close();
    }
}