🚀 [PALINDROMIZE] 문제 😊😊😊😊😊
앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “anonona”를 만들 수도 있고, “a”를 붙여서 “anona”를 만들 수도 있지요. 물론 S를 뒤집은 문자열을 S 뒤에 붙이면 항상 팰린드롬이 되므로, 결과 팰린드롬이 가능한 한 짧았으면 합니다.
S가 주어질 때 S에서 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하세요.
🔑 [풀이]
KMP알고리즘을 이용하여 두문자열이 주어졌을때 오버랩되는 최대문자수를 구해
원래 문자열의 길이와 reversed 문자열의 길이의 합을 오버랩되는 최대문자수를 빼준다.
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 C(<=50)가 주어집니다. 그 후 각 테스트 케이스마다 문자열 S가 주어집니다. 주어지는 문자열의 길이는 1 이상 10만 이하이며, 알파벳 소문자로만 구성됩니다.
🖥 출력
각 테스트 케이스마다 한 줄에 S를 이용해 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력합니다.
🖱 입력 예제
3
there
amanaplanacanal
xyz
💻 출력 예제
7
21
5
💎 전체 코드는 다음과 같습니다.
//
// PALINDROMIZE.cpp
// AALGGO
//
// Created by inhyeok on 2021/12/02.
//
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("PALINDROMIZE.txt");
/*
N에서 자기 자신을 찾으면서 나타나는 부분일치를 이용해
p[]를 구한다.
p[i] = N[..i]의 접미사도 되고, 접두사도 되는 문자열의 최대 길이
*/
vector<int> getPartialMatch(const string& N){
int m = N.size();
vector<int> pi(m,0);
// KMP 로 자기 자신을 찾는다
// N을 N에서 찾는다. begin = 0 이면 자기 자신을 찾아버리니깐 안됨!
int begin =1, matched = 0;
while(begin+matched < m){
if(N[begin+matched] == N[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 maxOverlap(const string& original, const string& reverse){
int n = original.size(), m = reverse.size();
vector<int> pi = getPartialMatch(reverse);
int begin = 0, matched= 0;
while(begin<n){
// 거꾸로한거랑 원래 문자열이 같다면
if( matched<m && (original[begin+matched] == reverse[matched])){
matched++;
// 기저사례 n까지 도달했을때
if(begin+matched == n){
return matched;
}
}
// 다르면
else{
// matched 한게 0 이면 시작점 증가.
if(matched == 0){
begin++;
}
// matched - pi[matched-1] 까지 돌아가 다시 시작한다.
else{
begin += matched - pi[matched-1];
matched = pi[matched-1];
}
}
}
return 0;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
string input;
string reverse;
fin >> input;
for(int i=0; i<input.size(); i++){
reverse += input[input.size() - i -1 ];
}
cout << input.size() + reverse.size() - maxOverlap(input,reverse) << endl;
}
}
Comments