[BOJ] 백준 4354번 문자열 제곱 (Java)

#4354 문자열 제곱

난이도 : 플레 5 

유형 : 문자열 / KMP

4354번: 문자열 제곱

▸ 문제

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

▸ 입력

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

▸ 출력

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

 

문제 풀이  

단순 주어진 문자열의 부분 일치 테이블을 구하여 마지막 접미사의 크기(table[n-1])을 반환하면 되는 문제인 줄 알았지만 아니었다. ababab의 같은 경우 (0 0 1 2 3 4) 테이블이 생성되는데 답은 ab^3이다. 중복되는 케이스도 고려해줘야 한다.

 

이럴 때 제일 간단한 방법은 문자열을 원형으로 확장시켜서 원본이랑 대조시키는 것이다. 'abababababab'로 펼친 문자열에 원본 'ababab'를 대입하여 KMP알고리즘으로 총 몇 번 매칭되는지 확인하면 a^n을 구할 수 있다. (마지막은 중복이므로 제외)

 

'ababab' KMP 매칭 예시

a

b

a

b

a

b

a

b

a

b

a

b

count

a

b

a

b

a

b

1

a

b

a

b

a

b

2

a

b

a

b

a

b

3

a

b

a

b

a

b

중복

 

'aaaa' KMP 매칭 예시

a	a	a	a	a	a	a	a	count
a	a	a	a					1
	a	a	a	a				2
		a	a	a	a			3
			a	a	a	a		4
				a	a	a	a	중복

 

'abcd' KMP 매칭 예시

a	b	c	d	a	b	c	d	count
a	b	c	d					1
				a	b	c	d	중복

 

설계

1. 주어진 문자열(pattern)을 원형 문자열(parent)로 확장하여 KMP알고리즘을 동작시킨다.
   
   1. parent = pattern+pattern;
2. idx>0 일치하는 문자가 발생했을 때, 연속적으로 더 일치하지 않으면 idx = table[idx-1];로 돌려준다.
3. if(pattern.charAt(i) == pattern.charAt(idx)) 두 위치의 문자가 일치하면  idx값을 올려 table[i]에 저장한다.
   1. parent의 특정 구간과 pattern의 모든 문자열이 매칭되었으면 cnt를 해준다.
4. (a^cnt)의 cnt를 출력한다.

 

풀이 코드 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String line = null;
		while(!(line = br.readLine()).equals(".")) {
			sb.append(KMP(line+line, line)+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static int KMP(String parent, String pattern) {
		int n1 = parent.length();
		int n2 = pattern.length();
		int[] table = makeTable(pattern);
		int cnt=0;
		int idx=0;
		for(int i=0; i<n1-1; i++) {
			while(idx>0 && parent.charAt(i) != parent.charAt(idx)) {
				idx = table[idx-1];
			}
			if(parent.charAt(i) == pattern.charAt(idx)) {
				if(idx == n2-1) {
					cnt++;
					idx = table[idx];
				}else {
					idx+=1;
				}
			}
		}
		return cnt;
		
	}
	static int[] makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		int idx=0;
		for(int i=1; i<n; i++) {
			while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				table[i] = ++idx;
			}
		}
		return table;
	}
}