문제 개요: 가장 짧은 회문 만들기
문자열 s가 주어졌다고 가정해 보겠습니다. 우리는 이 문자열의 앞쪽에만 문자를 추가하여 회문(팰린드롬)으로 바꿀 수 있습니다. 이때 만들 수 있는 회문 중 가장 짧은 것을 찾는 것이 목표입니다.
예를 들어 문자열이 "abcc"라면, 앞에 "ccb"를 추가하여 "ccbabcc"라는 가장 짧은 회문을 얻을 수 있습니다.
핵심 아이디어: KMP 알고리즘의 LPS 배열 활용
이 문제는 KMP 문자열 검색 알고리즘에서 사용되는 LPS(Longest Proper Prefix which is also Suffix) 배열을 응용하면 O(n) 시간 복잡도로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
원본 문자열 s와 뒤집은 문자열을 "#" 구분자로 연결합니다. (예: "abcc#ccba")
이 문자열의 LPS 배열을 계산하면, 마지막 값은 "s의 접두사이면서 동시에 s의 역순 문자열의 접미사인 최장 길이", 즉 s에서 가장 긴 회문 접두사의 길이를 나타냅니다.
s에서 회문이 아닌 나머지 꼬리 부분을 잘라내어 뒤집은 뒤 앞에 붙이면, 가장 짧은 회문이 완성됩니다.
알고리즘 단계별 풀이
n := s의 길이, s1 := s, s2 := s로 초기화합니다.
s2 문자열을 뒤집습니다.
s2 := s + "#" + s2 형태로 연결합니다. 여기서 "#"은 원본과 역순 문자열이 서로 섞여 잘못된 매칭이 발생하는 것을 막아주는 구분자 역할을 합니다.
s2와 같은 크기의 lps 배열을 선언합니다.
j := 0, i := 1로 초기화합니다.
i가 s2의 길이보다 작은 동안 다음을 반복합니다.
s2[i]와 s2[j]가 같다면, lps[i] := j + 1을 저장하고 i와 j를 각각 1씩 증가시킵니다.
같지 않다면, j > 0일 때 j := lps[j - 1]로 되돌아가고, j가 0이라면 i를 1 증가시킵니다.
extra := s의 lps 배열 마지막 값 인덱스부터 문자열 끝까지의 부분 문자열로 설정합니다. 이 부분이 회문에 포함되지 않는 꼬리 영역입니다.
extra를 뒤집습니다.
extra + s를 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
string s1 = s;
string s2 = s;
reverse(s2.begin(), s2.end());
s2 = s + "#" + s2;
vector <int> lps(s2.size());
int j = 0;
int i = 1;
while(i <s2.size()){
if(s2[i] == s2[j]){
lps[i] = j + 1;
j++;
i++;
} else {
if(j > 0){
j = lps[ j - 1];
} else {
i++;
}
}
}
string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]);
reverse(extra.begin(), extra.end());
return extra + s;
}
};
main(){
Solution ob;
cout << (ob.shortestPalindrome("abcc"));
}
입력
"abcc"
출력
ccbabcc
마무리 정리
모든 경우를 단순히 시도하면 O(n²) 이상의 시간이 걸릴 수 있지만, KMP의 실패 함수(LPS 배열)를 활용하면 문자열 길이에 비례하는 O(n) 시간 안에 가장 짧은 회문을 구할 수 있습니다. 문자열 처리 문제에서 자주 등장하는 패턴이므로 LPS 배열의 동작 원리를 함께 익혀두면 다른 알고리즘 문제 해결에도 큰 도움이 됩니다.