백준 문자열제곱 4354

 

https://www.acmicpc.net/problem/4354

4354번: 문자열 제곱

 

 

KMP 알고리즘에서 사용되는 prefix 테이블을 이용하여 풀 수 있는 문제다.

 

prefix테이블이란 문자열의 접두어(prefix)와 접미어(suffix)의 최대 겹치는 길이를 저장하는 테이블이다.

 

ACACABCACA 라는 길이가 10인 문자열을 사용해서 prefix 테이블가 무엇인지 또 어떻게 만드는지에 대해서 설명하겠다.

 

prefix 테이블을 만들기 위해서는 두개의 포인터가 필요하다.편의상 i,j라고 하고 i는 문자열 전체를 탐색하는 포인터, j는 i에 저장될 index를 저장할 포인터 정보이며, i는 1부터 j는 0부터 시작한다.

1)

j	i
A	C	A	C	A	B	C	A	C	A
0	0	0	0	0	0	0	0	0	0

 

s[j]! = s[i] 이므로 i만 증가시킨다. 

2)

j		i
A	C	A	C	A	B	C	A	C	A
0	0	1	0	0	0	0	0	0	0

 

s[j] = s[i] 이므로 prefix[i]에 j+1를 저장하고 i와 j모두 증가시켜준다.

prefix[2] =1 이라는 말은 

ACA라는 문자열에 prefix = suffix가 같은 길이가 1인 부분 문자열이 있다는 뜻이다.(이 경우 A이다.)

 

3)

 

	j		i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	0	0	0	0	0	0

s[j] = s[i] 이므로 prefix[i]에 j+1를 저장하고 i와 j모두 증가시켜준다.

prefix[3] =2 이라는 말은 

ACAC라는 문자열에 prefix = suffix가 같은 길이가 2인 부분 문자열이 있다는 뜻이다.(이 경우 AC이다.)

 

4)

		j		i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	3	0	0	0	0	0

s[j] = s[i] 이므로 prefix[i]에 j+1를 저장하고 i와 j모두 증가시켜준다.

prefix[4] =23 이라는 말은 

ACACA라는 문자열에 prefix = suffix가 같은 길이가 3인 부분 문자열이 있다는 뜻이다.(이 경우 ACA이다.)

 

5) 

			j		i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	3	0	0	0	0	0

s[j] != s[i]이다.

이 경우 s[i]!=s[j] 가 만족할때까지 j를 prefix[j-1]로 옮긴다.

prefix [j-1] = 1 로 j를 1로 옮겼기만 C!= B이므로

다시 prefix[j-1] =0 으로 옮겼깆만 A!=B 이다.

그러므로 prefix[5] = 0 이다.

끝까지 못찾았으므로 i만 증가시킨다.

(ACACAB에서 직접 보면 알겠지만 prefix = suffix인 부분문자열을 찾을수 없다.)

 

 

6)

j						i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	3	0	0	0	0	0

s[j] != s[i]이다. i 만 증가시킨다.

 

7)

 

j							i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	3	0	0	1	0	0

 

s[i] ==s[j] 이다. i,j모두 1씩 증가시킨다.

ACACACABCA에서 prefix= suffix인 최대길이 부분 문자열은 1이다. (A)

 

8)

 

	j							i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	3	0	0	1	2	0

 

s[i] ==s[j] 이다. i,j모두 1씩 증가시킨다.

ACACACABCAC에서 prefix= suffix인 최대길이 부분 문자열은 2이다. (AC)

 

9)

		j							i
A	C	A	C	A	B	C	A	C	A
0	0	1	2	3	0	0	1	2	3

s[i] ==s[j] 이다. i,j모두 1씩 증가시킨다.

ACACACABCACA에서 prefix= suffix인 최대길이 부분 문자열은 3이다. (ACA)

 

이과정을 코드로 나타내면 다음과 같다.

for(i =1 ;i <input.length();i++) {
				
				while(j>0 && input.charAt(i)!=input.charAt(j)){
					j= prefix[j-1];
				}
				if(input.charAt(i)==input.charAt(j)) {
						prefix[i] = j+1;
						j++;
				}
			}

 

 

 

이제 prefix 테이블을 이용해서 문자열 제곱문제를 풀어보자

 

위에서 만들어진 prefix테이블을 통해 prefix = suffix 인 최대길이 부분문자열 정보를 가지고 있다.

 

그렇다면 prefix [len-1]에는 문자열 전체의 prefix = suffix인 최대길이 부분문자열이 들어있을것이다.

 

ABCABCABC 라는 문자열이 있다면

prefix table은

000123456 으로

len = 9

prefix[len-1] = 6이다.

편의상 [x : y]를 x부터 y까지의 부분문자열이라고 가정하면

 

[0 : 6] = [len-1-6 : len-1] 이 성립하므로

[0 : len- prefix[len-1]] = [0 : 3] 이 문자열에서 반복한다는 것을 알수 있다..

단 len % prefix[len-1] !=0인 경우 중간에 다른 문자가 껴있는 경우이므로 거듭제곱이 성립하지 않는다.

 

예를 들어 ABCDABC의 경우 prefix[len-1] = 3이고, len =7 이므로 7%(7-3)!=0이다.

반면 ABCABCD의 경우 prefix[len-1] = 4이고 len=8이므로 8%(8-4)==0이다.

 

이 원리를 이용하면 쉽게 문자열 최대 거듭제곱을 구할수 있다.

package 백준;

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

public class 문자열제곱 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}
	public static void main(String[] args) throws Exception{
		//System.setIn(new FileInputStream("res/문자열제곱.txt"));
		MyScanner sc = new MyScanner();
		String input;
		while(true) {
			input = sc.next();
			if(input.equals(".")) break;
			int prefix[] = new int[input.length()];
			int i ,j=0;
			for(i =1 ;i <input.length();i++) {
				
				while(j>0 && input.charAt(i)!=input.charAt(j)){
					j= prefix[j-1];
				}
				if(input.charAt(i)==input.charAt(j)) {
						prefix[i] = j+1;
						j++;
				}
			}
			
		//	for(i =0 ;i <prefix.length;i++) {
		//		System.out.print(prefix[i] + " ");
		//	}
		//	System.out.println();
			
			int len = input.length();
			
			boolean flag = true;
			int answer = 0;
			int end = prefix[len-1];
			if(end==0) {
				flag = false;
			}else {
				if(len%(len-end)!=0) flag = false;
				else answer = len/(len-end);
			}
			//System.out.printf("prefix =%d d=%d\n",prefix[len-1],d);
			if(!flag) System.out.println("1");
			else System.out.println(answer);
		}
		
	}
}