일단 직관적으로 생각해봅시다. 주어진 문자열에서 앞에서부터 되는 대로 짝수 길이의 palindrome이 보이자마자 잘라내어도 상관없을 것 같지 않나요? 구체적으로는 이렇습니다. 주어진 문자열을 n, 잘라낸 palindrome을 x라 하고, 남은 문자열을 y라 합시다.
문자열 x는 짝수 길이 palindrome들의 곱이다. (하나의 짝수 길이 palindrome으로만 이루어졌다고 해도, pi * x = x로 볼 수 있으니까요)
y가 짝수 길이 palindrome들의 곱이면, 당연히 n = x * y니까 n은 짝수 길이 palindrome들의 곱이다.
n이 짝수 길이 palindrome들의 곱이면, y도 짝수 길이 palindrome들의 곱이다.
pf) x = x_1 * x_2 * ... * x_p 라 합시다. 이 때 x_i는 더이상 작은 짝수 길이 palindrome들로 분해되지 않는 가장 작은 짝수 길이 palindrome이라고 합시다. 이런 것을 이하 prime palindrome이라고 합시다.
n = n_1 * n_2 * ... * n_q 라 합시다. 1 <= i <= p에 대해, x_i = n_i일까요? 상식적으로는 당연히 그렇지만 엄밀하게 증명해 봅시다. 즉, x_i != n_i라면 x_i가 n_i의 prefix이거나, 혹은 그 반대일 것이므로 어떠한 prime palindrome도 다른 prime palindrome의 prefix일 수 없음을 보이면 됩니다.
두 prime palindrome을 각각 a * a^R, b * b^R 이라 하고, b는 a의 prefix인 prime palindrome중 가장 작은 것으로 합시다. 즉, a * a^R = b * b^R * c 입니다.
i) |a| < |b * b^R|
a * d = b * b^R로 둡시다. 따라서 준식에서, a * a^R = b * b^R * c = a * d * c 입니다. a^R = d * c 겠죠.
한편, (b * b^R)^R = b * b^R = d^R * a^R = d^R * d * c 입니다.
a * a^R = d^R * d * c * c 인데, d^R * d는 짝수 길이 palindrome이므로 최소 반례 조건에 위배됩니다.
ii) |a| >= |b * b^R|
a = b * b^R * d로 두고, a^R = d^R * b * b^R 에서 a * a^R = b * b^R * d * d^R * b * b^R = (b * b^R) * (d * d^R) * (b * b^R)입니다. a는 prime palindrome이어야 하는데 아니므로 모순입니다. 따라서 쭉 증명 끝.
그래서, 필요충분조건이니까 짝수 길이 palindrome을 앞에서부터 보이는 대로 잘라내면 됩니다. 만약에 길이가 n인 어떤 string에 대해서 prefix인 짝수 길이 palindrome을 linear time에 찾을 수 있다면,
n을 앞에서부터 1글자 잘라 짝수 길이 palindrome 탐색 알고리즘을 적용하고, 성공하면 잘라내고 반복한다. 실패하면,
n을 앞에서부터 2글자 잘라 짝수 길이 palindrome 탐색 알고리즘을 적용하고, 성공하면 잘라내고 반복한다. 실패하면,
n을 앞에서부터 4글자 잘라 짝수 길이 palindrome 탐색 알고리즘을 적용하고, 성공하면 잘라내고 반복한다. 실패하면,
n을 앞에서부터 8글자 잘라 짝수 길이 palindrome 탐색 알고리즘을 적용하고, 성공하면 잘라내고 반복한다. 실패하면,
...
n을 앞에서부터 n글자 잘라 짝수 길이 palindrome 탐색 알고리즘을 적용하고, 성공하면 잘라내고 반복한다. 실패하면,
을 반복해서 전체 탐색을 O(n)에 수행할 수 있습니다. 그래서, 짝수 길이 palindrome 탐색을 linear time에 할 수 있으면 됩니다.
느낌을 느끼기 위해서 아래 두 케이스를 생각해 봅시다.
{고정폭}
n : baabbabbaabaaxbaabbabbaab
n^R : baabbabbaabxaabaabbabbaab
n : baabbabbaabaaxbaabbabbaab
n^R : baabbabbaabxaabaabbabbaab
만약에 n과 n^R을 패턴 매칭 알고리즘을 사용해서 매칭해서, 텍스트(n^R)의 맨 마지막에서의 탐색된 패턴의 길이를 알아낸다면 그게 바로 largest prefix palindrome입니다. 왜냐면, 이 녀석을 p라 두면 n = p * q고, n^R = q^R * p^R = q^R * p 니까 p^R = p 입니다.
그.러.면. 이건 KMP같은 알고리즘을 사용하면 구할 수 있겠군요!
그런데, 사실은 위의 예제처럼 홀수 길이 palindrome이 검색될 수도 있습니다. 위의 예 말고도
n : aabaababaa
n^R : aababaabaa
n : aabaababaa
n^R : aababaabaa
이런 경우도 있을 수 있을 거구요. 조금 더 머리를 굴려 봅시다. KMP에는 failure function이 있습니다. KMP를 이해하셨다면 아시겠지만, 지금까지 i글자가 패턴이랑 완전히 일치하고, 다음 글자도 일치하면 좋겠지만 다음 글자가 일치하지 않으면 처음부터 다시 찾을 게 아니라 이 뒷부분에서 최대한 얻어낼 수 있는게 얼마나 큰지 미리 계산하고 그만큼만 포기하는 것이 KMP의 핵심입니다. 즉, 지금까지 매칭한 내용이 p라 하면 p의 prefix와 suffix가 같은 최대 길이를 구해둠으로써 얼마나 패턴을 슬라이드할지를 미리 계산하는 것이죠. 위의 예제에서 만약에 뒤에 한 글자가 더 있었다고 칩시다(palindrome 탐색과는 무관한 일반적인 매칭 문제로)
x : aabaababaa
y : aababaabaaO
x : aabaababaa
y : aababaabaaO
이렇게, aabaa에서 탐색이 실패하자 최대한 건져내어 aa부터의 패턴인가 확인하는 거죠. 따라서 위와 같은 원리를 적용해서, 맨 마지막 n^R의 suffix 부분이 홀수 길이 palindrome이라면 failure function을 사용해서 바로 그 다음 palindrome의 길이를 알아낼 수 있습니다. 그래서 이게 짝수 길이가 될 때까지 계속 찾아보다가 안 되면 포기하는 거죠.
꽤 어려운 문자열 문제였는데, KMP에 대한 이해가 충분했다면 쉽게 풀었을지도 모르겠네요. 특히 저 suffix-prefix 관계는 종종 나오기도 합니다. 이 문제는 바로 그 KMP 알고리즘이 소개된 Knuth, Morris, Pratt의 논문에 실렸던 문제 중 하나입니다.
Being
일단 직관적으로 생각해봅시다. 주어진 문자열에서 앞에서부터 되는 대로 짝수 길이의 palindrome이 보이자마자 잘라내어도 상관없을 것 같지 않나요? 구체적으로는 이렇습니다. 주어진 문자열을 n, 잘라낸 palindrome을 x라 하고, 남은 문자열을 y라 합시다.
15년 전