백준 5582번 : 공통 부분 문자열 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

공통 부분 문자열 골드 5

 

📖 문제

 

최장 공통 부분 수열 문제로

 

str1의 i번째 문자와 str2의 j번째 문자가 공통이라면 (같다면)

이전 문자까지 연속된 공통 부분 수열 + 1 (현재 공통 부분)

 

점화식

LCS[i][j] = LCS[i-1][j-1] + 1; (i >= 1, j >= 1)

 

---

🔅 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

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

        int str1Len = str1.length();
        int str2Len = str2.length();

        int[][] LCS = new int[str1Len + 1][str2Len + 1];
        int t = 0;

        for (int i = 1; i <= str1Len; i++) {
            for (int j = 1; j <= str2Len; j++) {
                // 공통 문자라면 
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    LCS[i][j] = LCS[i-1][j-1] + 1; // 이전까지의 연속된 공통 부분 수열 + 1 (현재 공통 문자 1개)
                }

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

        System.out.println(t);

    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.