[KMP] Shortest Palindrome - ㄹㅇ 어려움 주의 🥲
✨ 인사이트
Brute-force를 사용해서 (왼쪽부터 시작하는) 가장 긴 palindrome을 찾을 수 있다. 하지만 그것은 Time Complexity가 O(n^2)이다. 이보다 빠른 방법이 있다.
바로 KMP 알고리즘을 사용하는 것이다!
✨ 인사이트 - KMP 알고리즘
KMP 알고리즘은 특정 패턴이 주어진 텍스트 안에서 어디에 위치하는지 빠르게 찾는 방법이다.
이는 두 단계로 나뉜다.
1️⃣ LPS 배열 만들기
2️⃣ 이 배열을 활용해서 텍스트에서 패턴 찾기
LPS는 Longest Prefix which is also Suffix의 줄임말로, 0번째부터 k번째까지 (0 <= k <= len(s)-1) 자른 문자열의 앞에서부터 자른 문자열(prefix)들의 묶음과 뒤에서부터 자른 문자열(suffix)들의 묶음 중에서 가장 길게 겹치는 문자열의 길이를 입력한 배열이다.
말로 하면 어려우니 예시를 보자면,,
패턴 ABABC를 보자.
최초의 LPS 배열은 [0, 0, 0, 0, 0]이다.
편의상 LPS[0] = 0이다.
1번째까지 자른 문자열은 AB다.
prefix: A
suffix: B
겹치는 것은 없으므로 LPS[1] = 0이다.
2번째까지 자른 문자열은 ABA다. (ABA 전체를 자른 문자열이 아니라 "부분" 문자열임에 주의. 앞으로도 쭉 똑같다.)
prefix: A, AB
suffix: A, BA
겹치는 것 중 가장 긴 문자열은 A이므로 LPS[2] = 1이다.
3번째까지 자른 문자열은 ABAB다.
prefix: A, AB, ABA
suffix: B, AB, BAB
겹치는 것 중 가장 긴 문자열은 AB이므로 LPS[3] = 2이다.
4번째까지 자른 문자열은 ABABC다.
prefix: A, AB, ABA, ABAB
suffix: B, AB, BAB, BABC
겹치는 것은 없으므로 LPS[4] = 1이다.
따라서 LPS는 [0, 0, 1, 2, 0]이 된다.
이제 이 LPS를 가지고 텍스트에서 패턴을 찾아내자!
(우리가 풀 문제에서는 LPS 배열만 완성하는 것으로 충분하지만,, 그래도 KMP 알고리즘을 끝까지 알면 좋잖슴!!)
(원래 주저리주저리 썼는데 가독성이 안 좋아서 chatGPT 캡처로 대체함 ㅜㅜ)
👟 알고리즘 설명
1. 주어진 배열 s에 대해 s + "#" + s[::-1]을 만든다. (#은 둘을 구분하기 위해 끼웠다.)
2. 새롭게 만든 문자열에 대해 Prefix Table을 만든다.
def _build_prefix_table(s): #앞에 있는 언더스코어(_)는 이 함수는 클래스 내부에서만 쓰이기를 희망한다는 뜻
prefix_table = [0] * len(s) # Prefix Table을 s의 길이만큼 초기화
length = 0 # 일치하는 접두사와 접미사의 길이를 저장하는 변수
for i in range(1, len(s)): # 두 번째 문자부터 시작 (i = 1부터)
while length > 0 and s[i] != s[length]: # 불일치가 발생하면
length = prefix_table[length - 1] # 이전 접두사로 되돌아감
if s[i] == s[length]: # 일치하면
length += 1 # 접두사-접미사 길이를 증가
prefix_table[i] = length # Prefix Table에 길이를 저장
return prefix_table
# 접두사: prefix, 접미사: suffix
아래 예시를 하나씩 따라가며 이 과정이 어떻게 발생하나 보자.
그런데 여기서 주목해야 한다.
(아래 사진에 왜 숫자가 다시 1부터 시작하냐면 빌어먹을 chatGPT가 헛소리해서 고치느라 새로 만들어서 그렇다 ㅎ)
aaab에서 aaa와 aab를 비교했는데 이들이 같지가 않다. 그렇다면 한 단계 양보해야 한다. 이를 length는 2에서 1로 줄어든다.
그렇다면 이제는 aa와 ab를 비교해야 하는데 이 역시 같지가 않다. 다시 한 단계 양보한다. 그러면 length는 1에서 0으로 줄어들고 while문 조건에 맞지 않아 탈출하게 된다.
i=4부터 다시 진행된다.
그리고 다시 불일치가 발생한다.
이후 그냥 무난하게 흘러가서 최종적으로 다음과 같이 prefix_table이 나온다.
prefix_table = [0, 1, 2, 0, 1, 2, 0, 1, 2, 3]
3. combined string에 prefix table을 만들고 답을 구한다.
def shortestPalindrome(self, s: str) -> str:
# Reverse the original string
reversed_string = s[::-1]
# Combine the original and reversed strings with a separator
combined_string = s + "#" + reversed_string
# Build the prefix table for the combined string
prefix_table = self._build_prefix_table(combined_string)
# Get the length of the longest palindromic prefix
palindrome_length = prefix_table[-1]
# Construct the shortest palindrome by appending the reverse of the suffix
suffix = reversed_string[: len(s) - palindrome_length]
return suffix + s
prefix_table[-1]은 곧, 왼쪽에서부터 시작하여 가장 긴 palindrome의 길이를 나타낸다.
다시 방법을 정리하면,
1️⃣ 문자열 s를 가운데에 #이라는 delimiter를 두고 오른쪽에 거꾸로 붙인다
2️⃣ prefix table을 만든다(이것은 KMP 알고리즘의 한 단계인 "LPS 배열"을 만드는 것이다.)
3️⃣ prefix table[-1]이 가장 긴 palindrome이기 때문에 이를 통해 답을 구한다.
✅ 정답
Time Complexity: O(n)
Space Complexity: O(n)
class Solution:
def shortestPalindrome(self, s: str) -> str:
# Reverse the original string
reversed_string = s[::-1]
# Combine the original and reversed strings with a separator
combined_string = s + "#" + reversed_string
# Build the prefix table for the combined string
prefix_table = self._build_prefix_table(combined_string)
# Get the length of the longest palindromic prefix
palindrome_length = prefix_table[-1]
# Construct the shortest palindrome by appending the reverse of the suffix
suffix = reversed_string[: len(s) - palindrome_length]
return suffix + s
# Helper function to build the KMP prefix table
def _build_prefix_table(self, s: str) -> list:
prefix_table = [0] * len(s)
length = 0
# Build the table by comparing characters
for i in range(1, len(s)):
while length > 0 and s[i] != s[length]:
length = prefix_table[length - 1]
if s[i] == s[length]:
length += 1
prefix_table[i] = length
return prefix_table
그나저나, prefix table의 time complexity가 O(n)인 이유가 이해가 되지 않았다.
왜냐면 for 안에 while이 있는데 while은 하나씩 훑기 때문에 사실상 while 역시 n번 반복될 수 있기 때문이다.
하지만,, 그렇지 않다.
이런저런 설명들을 찾아보고 chatGPT한테도 물어봤는데 내가 생각하기에 가장 쉬운 생각법은 이것이다.
아래 사항들을 하나씩 음미해 보자.
- length가 (순순히) 1이 늘어난다는 것은 while문을 거치지 않았다는 뜻이다.
- length가 while문을 여러 번 반복할 수 있다. 하지만 그 최대 횟수는 현재의 length만큼 뿐이다.
whlie문은 기존의 length를 허무는 것밖에 하지 못한다.
그러니까 i가 1부터 점점 커갈 때, 예를 들어 1부터 k까지 열심히 쌓았는데 k+1에서 신나게 while문이 돌면서 length를 0까지 만든 k번의 추가적인 연산을 요구한다. 이 연산의 수는 1번부터 k번까지 고르게 1번씩 나눠줄 수 있기 때문에 i가 k+1까지 늘어나는 동안의 연산의 수는 최대 2k인 것이다!
즉, 이를 n까지 확대하면 O(n)이 time complexity가 된다.