[백준 / BOJ] 1498 주기문

문제

출처 : https://www.acmicpc.net/problem/1498

1498번: 주기문

어떤 문자열 X를 n번 연달아 쓴 것을 X^n으로 나타낸다. 

예를들어, 문자열, ababab는 ab^3이 된다.

 

문자열 X를 앞에서부터 i번째까지 주기문을 이룬다고 했을때, 해당 주기문의 n(n은 가능한 가장 크게)을 구하는 문제다.

 

예를들어, 문자열 abababab는

4 2

6 3

8 4

가 출력된다.

---

풀이

kmp로 푸는 문제였다.

주기를 찾는다는것은 반복되는 문자를 찾는다는의미 이므로 kmp를 이용해 문제를 풀수있었다.

 

예를들어, 문자열 abcabc를 kmp를 이용해 희소배열을 만들어보자.

문자 abcabc

배열 000123

희소배열에서 pi[5] = 3은 앞에서부터 3개의 접두사와 일치한다는것이므로, 위 문장에서 abc가 총 2개 나오는것을 알수있다.

pi[3], pi[4]는 각각 앞에서부터 1개, 2개의 접두사와 일치한다는 의미이지만, 주기문이 아니다. 

예를들어, i = 3 , pi[3] = 1 일때,

i = 3이므로, 이미 희소배열앞에 'abc'라는 길이 3의 글자가 존재한다. 따라서, abca는 주기문이 될수없다.

 

이를 통해, 다음과 같은 식을 생각할수있다.

접미사 길이 = pi[i]

접두사 길이 = (i+1) - pi[i] (i는 0부터 시작하기때문에 +1을 해줘야한다.)

if(접두사길이 % 접미사 길이 == 0) 답 = i+1 + " " + 접미사 길이 / 접두사 길이

 

kmp코드

    private void kmp(){
        int[] pi = new int[str.length()+5];
        int pIdx = 0;
        for(int idx = 1; idx < str.length(); idx++){
            while(str.charAt(idx) != str.charAt(pIdx) && pIdx > 0) pIdx = pi[pIdx-1];
            if(str.charAt(idx) == str.charAt(pIdx)) pi[idx] = ++pIdx;
        }
        for(int i = 1; i < str.length(); i++){
            int sufCnt = pi[i];
            int preCnt = (i+1)-pi[i];
            if(sufCnt % preCnt == 0 && sufCnt/preCnt > 0) 
                System.out.println((i+1) + " " + ((sufCnt/preCnt)+1));
        }
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/tree/master/1498%20%EC%A3%BC%EA%B8%B0%EB%AC%B8

devxb/JJUNalgo