[JAVA] 백준 1701번 : Cubeditor

 

---

 

• 코드

정답 코드 : KMP 알고리즘을 통해 풀었다. pi 배열을 통해 왼쪽부터 한 글자씩 제거한 문자열을 인자로 넣어 모든 가능한 부분문자열 중에서 접두사와 접미사가 같은 문자열의 최대 길이 를 구하면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		int n = s.length(), max = 0;
		
		for(int i = 0; i < n; i++) 
			max = Math.max(max, KMP(s.substring(i, n)));
		
		System.out.println(max);
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP(String s) {
		// j 접두사
		int j = 0, n = s.length(), max = 0;
		int pi[] = new int[n];
		
		// i 접미사
		for(int i = 1; i < n; i++) {
			while(j > 0 && s.charAt(i) != s.charAt(j)) 
				j = pi[j-1];
			
			if(s.charAt(i) == s.charAt(j)) 
				max = Math.max(max, pi[i] = ++j);
		}
		return max;
	}
}

 

• KMP 알고리즘

 

  1)  기본적인 문자열 탐색 알고리즘은 O(전체 문자열 길이 * 찾으려는 문자열 길이) 만큼 걸리지만, 이 KMP 알고리즘은 O(전체 문자열 길이 + 찾으려는 문자열 길이) 만 걸리는 효율적인 알고리즘이다.

 

  2)  이렇게 시간복잡도를 줄일 수 있는 이유는 바로 문자 하나씩 비교하는 것이 아니라 이전에 이미 비교했던 중간 부분을 건너뛰며 비교하기 때문이다.

 

  3)  찾고자 하는 문자열이 왼쪽부터 시작해서 가질 수 있는 모든 문자열들 중,  접두사와 접미사가 같은 문자열의 최대 길이를 구해서 이를 활용하는 알고리즘.

 

예를들어, tomato가 있다면

 

<접두사>

t

to

tom

toma

tomat

tomato

이 6개가 banana의 접두사(prefix) 입니다.

 

<접미사>

o

to

ato

mato

omato

tomato

이 6개가 banana의 접미사(suffix) 입니다.

 

여기서 접두사와 접미사를 를 비교해보면

t, o -> x

to, to -> o

tom, ato -> x

toma, mato -> x

tomat, omato -> x

tomato, tomato -> 자기자신은 당연히 일치하니까 애초에 비교대상에서 제외됨.

 

이렇게 비교해서 tomato란 문자열에서 접두사와 접미사가 일치하는 최대의 길이는 2가 된다.

 

<보다 잘 설명되어있는 링크> bowbowbow.tistory.com/6#comment5168448