백준 5582 - 공통 부분 문자열

Java

5582 번 - 공통 부분 문자열

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

접근 방법

구현

코드

/*
5582번 - 공통 부분 문자열
https://www.acmicpc.net/problem/5582
*/

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

public class Main {
	static int result = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	String a = br.readLine();
    	String b = br.readLine();
    	
    	int alen = a.length(), blen = b.length(); 
    	int[][] dp = new int[alen][blen];		// 각 문자열의 길이만큼 2차원 배열을 만든다.
    	
    	for(int i = 0; i < alen; i++) {
    		for(int j = 0; j < blen; j++) {
    			if(a.charAt(i) == b.charAt(j)) {
    				if(i == 0 || j == 0) {		// i, j 중 둘 중 하나라도 0이라면, i-1 or j-1이 -1이 되므로 IndexExecption이 되므로 방지
    					dp[i][j] = 1;
    				}
    				else {
    					dp[i][j] = dp[i-1][j-1] + 1;	// 현재 문자가 같으면, 직전 문자까지 동일한 두 부분 문자열 길이에 대해 1을 증가한다
    				}
    				result = Math.max(result, dp[i][j]);	// 문자열 길이 최대값
    			}
    		}
    	}
    	
    	System.out.println(result);
    	br.close();
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

Sliding Window로 실패한 코드

/*
5582번 - 공통 부분 문자열
https://www.acmicpc.net/problem/5582
*/

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

public class Main {
	static int result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String a = br.readLine();
    	String b = br.readLine();
    	
    	if(a.length() > b.length()) {
    		String temp = a;
    		a = b;
    		b = temp;
    	}
    	
    	String str;
    	int size = a.length();
    	int l = 0, r = 0;	// 왼쪽 선, 오른쪽 선
    	int pm = 1;			// 1씩 늘려갈지, -1로 줄여 나갈시
    	
    	while(true) {
    		r += pm;		// 오른쪽 선을 좌,우로 이동한다.
    		if(r > size) {	// 만약 오른쪽 선이 size를 넘어가면, 다시 왼쪽으로 줄여나간다
    			pm = -1;
    			l++;
    			if(l == size)
    				break;
    			continue;
    		}
    		if(r == l) {	// 만약 오른족 선이 left와 마주치면, 다시 오른쪽으로 늘려나간다.
    			pm = 1;
    			l++;
    			r++;
    			if(l == size)
    				break;
    			continue;
    		}
    		str = a.substring(l,r); // sliding window(l,r)로 문자열을 자른다.
			if(b.contains(str)) {	// 대상 문자열에 포함되어 있으면 길이 최대값
				result = Math.max(r - l, result);
			}
    	}
    	System.out.println(result);
    	br.close();
	}
}

총평

난이도

⭐★★★★

후기

이전에도 접했던 문제이기 때문에 쉽게 해결 가능했다.

개선할 점

없