예제: 팰린드롬 만들기
문제
앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “anonona”를 만들 수도 있고, “a”를 붙여서 “anona”를 만들 수도 있지요. 물론 S를 뒤집은 문자열을 S 뒤에 붙이면 항상 팰린드롬이 되므로, 결과 팰린드롬이 가능한 한 짧았으면 합니다.S가 주어질 때 S에서 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(<=50)가 주어집니다. 그 후 각 테스트 케이스마다 문자열 S가 주어집니다. 주어지는 문자열의 길이는 1 이상 10만 이하이며, 알파벳 소문자로만 구성됩니다.출력
각 테스트 케이스마다 한 줄에 S를 이용해 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력합니다.예제 입력
3 there amanaplanacanal xyz예제 출력
7 21 5
풀이
이전에 포스팅했던 NAMING 문제의 문자열 탐색 알고리즘(KMP 알고리즘)을 사용하는 문제이다.
전체적인 알고리즘은, 단어를 뒤집은 후 단어 순서대로 겹치는 부분이 얼마나 되는지를 구하면 된다.
이렇게 말하면 쉬워보인다. 실제로 반복문으로만 구현하면 쉬울지도 모르나, 시간초과에 걸릴 것이다.
예를 들어, 'there'를 반대로 뒤집으면 'ereht'가 된다. 여기서 there와 ereht가 there의 몇 번째 순서에서 겹치는지를 구한다. 위 예에서는 2가 될 것이다. 여기에 단어의 길이인 5를 더해주면 답이 된다.
KMP 알고리즘이 들어가는 부분은, 원래 단어와 뒤집은 단어가 어느 부분에서 겹치는지를 빠르게 탐색하기 위해 사용한다.
필자도 아직은 KMP 알고리즘을 거의 주입식마냥 외워서 사용하고 있다. 이해가 잘 되는 그 순간 시간을 내어 포스팅을 하도록 하겠다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> setPartialMatch(const string& rev) {
int m = rev.size();
vector<int> pi(m, 0);
int begin = 1, matched = 0;
while(begin + matched < m) {
if (rev[begin + matched] == rev[matched]) {
matched++;
pi[begin + matched - 1] = matched;
}
else {
if (matched == 0) {
begin++;
}
else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}
int palindromize(const string& word, const string& rev) {
vector<int> pi = setPartialMatch(rev);
int m = word.size();
int begin = 0, matched = 0;
while (begin + matched < m) {
if (word[begin + matched] == rev[matched]) {
matched++;
if (begin + matched == m) {
break;
}
}
else {
if (matched == 0) {
begin++;
}
else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return begin + m;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
string word, rev;
cin >> word;
rev = word;
reverse(rev.begin(), rev.end());
cout << palindromize(word, rev) << endl;
}
return 0;
}풀이 후기
KMP 알고리즘을 잘 알고 있다면 금방 풀 문제이긴 하나, 언제나 그렇듯이 그게 어렵다.
알고리즘의 자유로운 적용과 응용은 참 어려운 것 같다.
