[BOJ][C++] 백준 23304번: 아카라카

https://www.acmicpc.net/problem/23304

23304번: 아카라카

 

문제

아카라카!

아카라카(아라)칭 아카라카(아라)쵸 아카라카(아라) 칭칭

쵸쵸쵸 랄랄라 시스붐바 연세 선수 라플라

헤이 연세 야!

AKARAKA(아카라카)는 컴퓨터 과학적 관점으로 바라봤을 때, 튜링도 기립 박수를 치고 갈 가히 최고의 구호라 할 수 있다. AKARAKA는 그 자체로도 팰린드롬이고, 접두사이자 접미사인 AKA가 또한 팰린드롬이기 때문이다.

신촌에서는 AKARAKA같은 특성을 가진 팰린드롬을, 아카라카 팰린드롬이라 아래와 같이 정의한다.

1. 문자열 S$S$가 팰린드롬이다. 팰린드롬이란 거꾸로 뒤집어 읽어도 같은 문자열을 뜻한다.
2. 문자열 S$S$의 길이를 |S|$|S|$라 할 때, ⌊|S|2⌋$\lfloor\frac{|S|}{2}\rfloor$ 길이의 접두사와 접미사가 모두 아카라카 팰린드롬이다. 만약 |S|=1$|S| = 1$이면, S$S$는 아카라카 팰린드롬이다.

임의의 문자열이 주어졌을 때, 그 문자열이 아카라카 팰린드롬인지 알아보자. 만약 알아내지 못하면, 졸업할 때까지 아카라카를 못 갈지도 모른다!

입력

알파벳 소문자로 이루어진 문자열 S$S$가 주어진다. (1≤|S|≤2 000 000$1 \leq |S| \leq 2\ 000\ 000$)

출력

주어진 문자열 S$S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다.

만약 그렇지 않다면, IPSELENTI를 출력한다.

 

풀이

아라칭아라쵸아라칭칭쵸쵸쵸랄랄라시스붐바연세선수라플라헤이연세야

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

bool isAkaraka = true;

void recur(string s) {
    int l = s.size();
    
    if(l<=0) {
        return;
    }
    
    string pre = s.substr(0, l/2);
    string suf = s.substr(l-l/2);
    
    if(pre.compare(suf)!=0) {
        isAkaraka = false;
        return;
    }
    
    recur(pre);
    recur(suf);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    string s;
    cin >> s;
    
    recur(s);
    
    if(isAkaraka) {
        cout << "AKARAKA";
    } else {
        cout << "IPSELENTI";
    }

    return 0;
}

/*
 */