지난 깃갤 문제 해설.

문제는 다음 링크 참조: https://gall.dcinside.com/mgallery/board/view/?id=github&no=74495


## 개요

이 문제를 나이브하게 접근한다면 주어진 n개의 문자열에 대해 choose(n, 2)개의 조합을 모두 테스트해야만 해. 두 문자열의 교환 검사를 O(n²)번 수행해야 하니 다소 비효율적이야. 더 좋은 방법이 있는지 생각해보자.


## 관찰

먼저 두 문자열이 교환이 언제 가능한지 따져보자.


Example 1. 서로 교환되는 두 문자열 x, y의 길이가 각각 |x| = 4, |y| = 6 이라고 하자. 일반해를 구하기 위해 x = abcd, y = fghijk 로 두면 abcdfghijk = fghijkabcd 즉 a = f, b = g, c = h, d = i, f = j, g = k, h = a, i = b, j = c, k = d 이고, 연립 방정식을 풀면 x = abab y = ababab 꼴임을 알 수 있어.


example 1에서 ω = ab 라고 하면 x = ω², y = ω³ 이니까, 이런 현상이 일반적으로 일어나는건지 의심할만해.


Lemma 2. 두 문자열 x, y가 서로 교환된다면 어떤 문자열 ω와 자연수 m, n이 존재해서 x = ωᵐ, y = ωⁿ 이다.

증명. 일반성을 잃지 않고 |x| ≤ |y| 라고 가정할 수 있어. y의 길이에 대한 강한 수학적 귀납법을 이용할거야. 두가지 케이스를 고려하자. (i) |x| = |y| 인 경우. x = y 여야 하므로 ω = x, m = 1, n = 1 이 조건을 만족시켜. (ii) |x| < |y| 인 경우. 등식 x y = y x 의 앞부분에서 길이 |y| 만큼을 생각하자. y에서 x의 길이 만큼의 prefix를 버린 문자열을 z = drop(|x|, y) 라고 하면 y = x z 임을 알 수 있어. 또 x y = y x 의 뒷부분에서 길이 |y| 만큼을 생각하면 y = z x 야. 따라서 x z = z x, 다시 말해서 x와 z는 서로 교환돼. 또 x, z 중 긴것의 길이가 y보다 짧으니까 귀납가설에 의해 x = ωᵐ, z = ωⁿ 인 문자열 ω와 자연수 m, n이 존재해. 그러면 x = ωᵐ, y = x z = ωᵐ ωⁿ = ωᵐ⁺ⁿ. ∎


즉 서로 교환되는 문자열은 모두 어떤 순환마디 ω를 반복해서만 만들어질 수 있어. 게다가 ω는 x의 부분문자열이기 때문에, x와 y중 하나만 알고 있어도 ω가 될 수 있는 문자열을 크게 제한해.


Example 3. x = "ababab"라고 하자. x의 순환마디는 ω₀ = "ab"와 ω₁ = "abab", ω₂ = "ababab" 뿐이고, lemma 2에 의해 x와 교환 될 수 있는 문자열은 ω₀, ω₁, 혹은 ω₂의 반복으로 표현되어야만 해.


비록 example 3에서 조건을 만족시키는 순환마디가 유일하지는 않지만 ω₁ = ω₀², ω₂ = ω₀³ 이니까, 실질적으로 ω₀가 x와 교환되는 문자열들을 결정한다고 할 수 있어. 그러나 이렇게 최소순환마디가 나머지 모두를 대표하는 일이 항상 일어날까? 다음 정리를 통해서 이를 확인할 수 있어.


Lemma 4. (transitivity) x와 y가 서로 교환되고, y와 z가 서로 교환된다고 하자. y의 길이가 0보다 크다면 x와 z는 교환된다.

증명. |y| > 0 이므로, 어떤 n에 대해 |x| + |z| < n |y| 야. x, z는 각각 y와 교환되니 yⁿ과도 교환이 가능해. 따라서 x z yⁿ = yⁿ x z, z x yⁿ = yⁿ z x 두 등식에서 길이 |x| + |z|의 prefix를 생각하면 x z = take(|x|+|z|, yⁿ) = z x 이므로 x, z는 서로 교환돼. ∎


Lemma 5. x를 길이가 0보다 큰 문자열이라 하고, 어떤 m에 대해 x = ωᵐ를 만족하는 문자열 ω중 가장 짧은것을 최소순환마디 ω₀라고 하자 (ω₀가 x의 prefix 이므로 이는 유일하다). y가 x와 교환되는 문자열이라면 어떤 n에 대해 y = ω₀ⁿ이다.

증명. x = ω₀ᵐ이라고 할게. 당연하게도, ω₀는 x와 교환돼. 또 x와 y가 교환되고, |x| > 0 이니 lemma 4에 의해 y와 ω₀도 교환될거야. 그러면 lemma 2에 의해 어떤 ω, n, k가 존재해서 y = ωⁿ, ω₀ = ωᵏ 을 만족해. 따라서 x = (ωᵏ)ᵐ = ωᵏᵐ 이 되는데, ω₀를 x의 순환마디중 가장 짧은 문자열로 골랐기 때문에 km ≤ m이고 결국 k = 1, ω₀ = ω 여야해. 따라서 y = ω₀ⁿ 이야. ∎


## 알고리즘

lemma 4에 따르면 교환 관계를 길이가 0보다 큰 문자열로 제한하면 transitive하고, 교환 관계는 당연히 reflexive & symmetric 하기 때문에 equivalence relation이 된다는걸 알 수 있어. 그러니 choose(n, 2)개의 모두 조합을 테스트 할 필요 없이, 선형적인 갯수의 조합만 테스트해봐도 충분하고 (예를 들어, 연속적인 2개 문자열 쌍들이 교환되는지만 검사해도 충분해), 이렇게 하면 두 문자열의 교환 검사를 나이브하게 한다고 해도 O(sum of length)의 시간복잡도로 구현할 수 있어. 이 문제는 결과가 참인 입력에서 문자를 단 1개만 바꿔도 결과가 거짓으로 바뀔 수 있기 때문에, 이게 최적 시간복잡도일거야.


lemma 5를 이용하면 x y = y x 를 직접 비교하는 것 보다 교환 관계 검사를 조금 더 효율적으로, 문자열 길이 만큼의 문자 비교 횟수만으로 구현할 수 있어. 나는 이렇게 구현해봤어.

rep :: Int -> [a] -> [a] rep n xs = concat (replicate n xs) test :: [String] -> Bool test = \xs -> case filter (not . null) xs of [] -> True y:ys -> go y (y:ys) where go x ys = all p ys where g = foldl gcd 0 (map length ys) w = take g x p y = y == rep (length y `div` g) w

이 구현은 최소순환마디를 직접 찾진 않고, 문자열들의 길이의 gcd 길이 순환마디로 검사하는 방식이야.


## 최소순환마디 계산하기

주어진 문자열 x에 대해서 최소순환마디를 계산하는건 그리 어렵지 않아. x의 prefix 중에서 x와 교환되면서 길이가 가장 짧은걸 고르면 되니까. 하지만 이 과정도 효율적으로 수행하고 싶다면 생각보다 까다로워. 재밌게도, KMP 알고리즘을 활용한 멋진 풀이가 있었어 : https://gall.dcinside.com/mgallery/board/view/?id=github&no=74498


간단하게 설명하자면, x가 자기자신이 아닌 순환마디를 가질 때 x의 최소순환마디의 길이는 x의 길이에서 failure function의 마지막 값을 뺀것과 같아.


Example 6. x = "abcabcabc"의 failure function

i 0 1 2 3 4 5 6 7 8 x[i] a b c a b c a b c F[i] 0 0 0 1 2 3 4 5 6



증명은 머리아파서 안해봤어


## 번외 : Agda 증명


위에서 소개한 몇개 보조정리가 Agda로 증명돼있어 : https://github.com/damhiya/AgdaFormalLanguage/blob/master/FormalLanguage.agda