백준 1701 (Cubeditor)

문제

---

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

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

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

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

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

 

 

 

 

풀이

---

conpulake.tistory.com/58?category=853119

백준 1786 (찾기)

위 문제에서 다룬 KMP 알고리즘을 이용해서 문제를 풀 수 있다.

 

KMP 알고리즘은 접두사와 접미사를 비교하여 가장 길게 반복되는 문자열을 찾는다.

 

이문제는 모든 문자열에서 가장 긴 반복되는 문자열을 찾아야한다.

 

따라서 문제에서 KMP알고리즘을 사용하려면 문자열을 앞에서 부터 하나씩 줄여가며 비교해주어야한다.

앞의 시작문자가 같으면 항상 같은 접두사가 나오기 때문에 중간에서부터 반복되는 문자열은 찾을 수가 없기 때문이다.

 

<전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	static int max = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		String string = bufferedReader.readLine();
		
		for(int i = 0 ; i < string.length() - 1; i++) {
			max = Math.max(findMax(string.substring(i)), max);
		}
				
		System.out.println(max);
	}
	
	static int findMax(String string) {
		
		int j = 0;
		int len = string.length();
		
		int[] table = new int[len];
		int max = 0;
		for(int i = 1 ; i < len ; i++) {
			while(j > 0 && string.charAt(i) != string.charAt(j)) {
				j = table[j - 1];
			}
			
			if(string.charAt(i) == string.charAt(j)) {
				table[i] = ++j;
				max = Math.max(j , max);
			}
		}
		
		return max;
	}
	
}