[BOJ 3779] 주기

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

---

1. 접근

 실패한 접근: 1~N/2까지 brute force로 반복하는지 탐색. 문자열이 길어지자 너무 속도가 느려졌다.

=> KMP 알고리즘을 이용해 해결

KMP 알고리즘을 이용하면, 어떤 문자열 A의 몇번째 글자까지 Prefix와 Suffix가 일치하는지 구할 수 있다.

문제의 TC#2였던 aabaabaabaab를 예시로 들면,

 - len=2 "aa"는 첫 번째 글자까지 같음. (aa)

 - len=3 "aab"는 없음 (aab)

 - len=4 "aaba"는 첫 번째 글자까지 같음 (aaba)

 - len=5 "aabaa"는 두 번째 글자까지 같음 (aabaa)

 - len=6 "aabaab"는 세 번째 글자까지 같음 (aabaab)

여기서 {0, 1, 0, 1, 2, 3}을 구할 수 있는 알고리즘이다.

---

2. 과정

 먼저 KMP 알고리즘을 이용해 테이블을 만들어야한다. (KMP에 대한 자세한 설명은 이 링크를 참조)

간단하게 설명해보려고 했는데 문자열 관련 알고리즘이다 보니 좀 난해해지긴 했는데 대충 다음과 같다.

 

[배경]

 - 일반적으로 이 테이블을 만들려면, 비교하려는 접두사 길이 'pre_len'과 문자열 길이 'str_len'에 대해,

   [0, pre_len)과 [str_len-pre_len, str_len)을 비교해야한다.

 - 이 경우, pre_len을 str_len/2까지 1씩 늘려가며 반복해야하고, 문자열 길이도 2~본문 길이 까지 반복된다.

   즉, 대충 O(N^3)정도의 시간 복잡도를 가지게 되는데 본문 길이가 10^6 이라면, 10^18번의 연산을 한다.

 - 그래서, 이전 비교의 결과를 이용해 계산 횟수를 줄이기 위한 알고리즘이 KMP 알고리즘이다.

 

[내용]

- 만약, "ABABC"라는 문자열에 대해 길이 2~5까지의 테이블을 구해보자.

• len=1은 검사하지 않는다. table[0] = 0
• len=2에서, "AB"이므로 불가능하다. table[1] = 0
• len=3에서, "ABA"이므로, 'A'가 가능하다. table[2] = 1
• len=4에서 "ABAB"이므로 'AB'가 가능하다. table[3] = 2
• len=5에서 "ABABC"이므로 불가능하다. table[4] = 0

 - 일반적인 방식을 사용한다면, len=5일 때 len[0] == len[2], len[1] == len[3]을 진행 한 뒤, len[2] != len[4]를 알게 된다.

   연산 순서를 뒤집는다 해도, 길이가 길어지고 틀린 문자열이 중간쯤에 있으면 많은 연산을 하는 것은 같다.

 

 - 그렇다면 KMP에서는 어떻게 할까?

   먼저, len=3일 때 한 글자가 일치 했음을 알았으므로, len=4는 두 번째 글자부터 비교한다.

    len=3에서 len[0] == len[2]가 이미 증명되서 한 글자가 일치했으므로,

    len=4는 len[1] == len[3]만 증명하면 두 글자 일치임이 자명하다.

 

 - 다음으로, len=5를 확인해보자.

   len=4일 때, 두 글자가 일치했으므로, len=5는 세 번째 글자부터 비교한다.

   len[2]("A") != len[4]("C") 이므로, 일단 세 개가 일치하지는 않는다.

   다음으로는, table에서 세 번째 글자에 대응되는 table[2]의 값을 가져와 그 값에 대응하는 순서의 글자와 비교한다.

 

-  여기서는, table[2] = 1이므로, 두 번째 글자인 B와 비교한다.

   len[1]("B") != len[4]("C") 이므로, table[1]의 값을 가져오면, len[0]("A") != len[4]("C") 이고, 

   index가 1 미만이 되었으므로, 더 이상 이전의 값을 가져오지는 않는다.

   => table[4] = 0 이 된다.

 

 - 그렇다면, 세 번째 글자가 틀린 것과 table[2]를 가져온 것에는 무슨 상관관계가 있을까?

   위의 짧은 예시로는 설명이 힘들어서 'AB'를 하나만 더 늘려보자.

   'ABABABC'가 있다고 해보자. 그러면 C에서 비교한 것은 'ABAB'(C) 일 것이다.

   여기서 가장 마지막 문자는 'B'였기 때문에,

   C의 왼쪽 글자도 ABAB에서 파란 부분을 없애서 'AB'와 비교를 해야한다. ( C의 왼쪽 마지막 글자가 B였으므로 )

   그리고 B로 끝나는 모든 부분 그룹과 비교를 해도 없으면, 마지막 B의 왼쪽으로 가면서 비교하는 것이다.

   위에 첨부한 링크로 가서 표를 따라가며 시뮬레이션 해보면 어느정도 이해가 될 거라고 생각한다... 설명력이 부족해서 ㅠㅠ

 

아무튼 KMP를 통해 문자열을 탐색하는 코드는 다음과 같다.

static int[] makeTable(char[] chars) {
    int index = 0;
    int[] table = new int[chars.length];
    for(int pos = 1 ; pos < chars.length ; pos++) {
        while(index > 0 && chars[index] != chars[pos]){
            index = table[index-1];
        }
        if(chars[index] == chars[pos]){
            table[pos] = ++index;
        }
    }
    return table;
}

설명의 길이에 비해 굉장히 간단한 코드...

 

 그리고 이렇게 구한 '일치하는 접두와 접미의 길이'를 가지고 어떻게 반복되는 횟수를 구할 것인가? 하는 문제가 남았다.

여기서 중요한 부분은 '일치하는 접두와 접미'이다. 즉, 접두와 접미가 똑같으므로, 일치하는 부분의 길이가 본문에서 접미를 뺀 부분의 길이로 나누어 떨어진다면, 그 몫만큼 반복한다고 판단할 수 있을 것이다.

 

예를 들어, 'aabaabaabaab'는 'aabaabaab'가 일치한다.

본문의 길이(12) - 일치하는 부분의 길이(9) = 3이 되고, 일치하는 부분의 길이(9) % 남은 접두의 길이(3) == 0 일 경우,

일치하는 부분은 남은 접두가 반복된 것이라는 것을 알 수 있다.

 

코드는 다음과 같다.

int[] kmp_table = makeTable(chars);

for(int pos = 1 ; pos < chars.length ; pos++) {
    if(kmp_table[pos] == 0) continue;
    int prefix_length = (pos+1) - kmp_table[pos];
    if(prefix_length > 0 && kmp_table[pos] % prefix_length == 0)
        out.append(pos+1).append(' ').append((pos/prefix_length)+1).append('\n');
}

 

 수학도 그렇듯이 숫자만 만지는게 아니라 문자가 들어가기 시작하면 알고리즘도 복잡해지는 것 같다.

 특히, 새로배우는 알고리즘의 경우 처음부터 100% 이해하는 것이 아니고

60%정도 이해해서 문제를 푼다음, 글을 쓰면서 한 80%까지 이해하게 되는 것 같은데 그렇다보니 글도 같이 난해해 지는 것 같다... 미래의 나는 현재의 내 글들을 보고 무슨 생각을 할까..

 

 

---

3. 코드