문제링크 입니다

🚀 [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;
    }
}

PALINDROMIZE

Comments