[BOJ] 1701 Cubeditor

문제

문제 설명

Baekjoon Online Judge - 1701번 Cubeditor

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

출력

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

풀이

해설

문자열의 모든 가능한 서브 문자열에 대해 KMP 시도하여 일치하는 문자열 길이의 최댓값을 구한다.

KMP에서는 문자열의 0번째 인덱스부터 접두사로 설정하여 문자열 일치 여부를 검사하므로, 서브 문자열은 원본 문자열의 맨 앞에서부터 문자 하나씩 지워가며 구성해야 한다.

시행착오

이미 등장한 적 있는 문자가 또 등장했다면 앞서 등장한 지점부터 현재까지의 문자열이, 반복되는 서브 문자열이 될 가능성이 있다고 생각.

따라서 이러한 문자열들만 리스트에 담아 KMP를 시도했는데 두가지 문제가 있었음.

• 일치하는 부분이 자기 자신이 떼어져 나온 바로 그 위치라면 중복되는 것이 아님
• 일치하는 부분이 통째로 일치하지 않고 일부 일치하는 경우 체크가 어려움

따라서 실패…

코드

import java.io.*;

public class BOJ_1701_Cubeditor {
	static String str;
	static char[] subChars;
	static int strLen, subLen, maxLen;
	static int[] returnPointer;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();
		strLen = str.length();
		
		findSubStrs();
		System.out.println(maxLen);
	}

	private static void findSubStrs() {
		for (int i=0; i<strLen-1; i++) {
			subChars = str.substring(i, strLen).toCharArray();
			subLen = subChars.length;
			returnPointer = new int[subLen];
			
			makeReturnPointerArr(i);
		}
	}

	private static void makeReturnPointerArr(int s) {
		for (int i=1, j=0; i<subLen; i++) {
			while (j>0 && subChars[i]!=subChars[j]) j = returnPointer[j-1];
			if (subChars[i]==subChars[j]) {
				returnPointer[i] = ++j;
				maxLen = Math.max(maxLen, j);
			}
		}
	}

}

💡

• 뭔가 시행착오로 실패한 로직 잘 구현하면 통과할 수도 있을 것 같은데,, 다시 도전해봐야 겠다.