Make superpalindrome! Batch
Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
---|---|---|---|---|---|
200 ms | 16 MiB | 50 | 18 | 9 | 50.00% |
펠린드롬을 아는가? 펠린드롬이란 문자열들 중에서 앞으로 읽는 것과 뒤로 읽는 것이 같은 문자열을 의미한다. 예를 들어 madam 의 경우 앞으로 읽어도 madam 이며 뒤로 읽어도 madam 이므로 펠린드롬인 것이다. 펠린드롬들 중에서도 슈퍼펠린드롬이 라는 것이 있는데, 슈퍼펠린드롬은 다음과 같이 재귀적으로 정의된다.
- 슈퍼펠린드롬은 모두 펠린드롬이어야 한다.
- 길이가 1 인 문자열은 모두 슈퍼펠린드롬이다.
- 길이가 짝수인 경우 문자열을 절반으로 쪼갰을 때, 앞의 절반과 뒤의 절반이 모두 슈퍼펠린드롬이어야 한다.
- 길이가 홀수인 경우 가장 중앙에 있는 문자를 제외하고 절반으로 쪼갰을 때, 앞의 절반과 뒤의 절반이 모두 슈퍼펠린드롬이어야 한다.
예를 들어 aa 의 경우 앞의 절반과 뒤의 절반이 모두 문자열 a 이며, 이는 길이가 1 이므로 슈퍼펠린드롬이다. 즉 aa 는 슈퍼펠린드롬인 것이다. 그러므로 aaaa 와 aabaa 도 슈퍼펠린드롬임을 알 수 있다. (aabaa 의 경우 가장 중앙의 b 를 제외하고 절반으로 쪼개면 앞의 절반과 뒤의 절반이 모두 aa 이므로 슈퍼펠린드롬인 것이다.)
알파벳 소문자로 이루어진 $L$자리의 문자열이 주어진다. 소문자로 이루어진 문자열들 중에 주어진 문자열 보다 사전순으로 뒤에 있고 길이가 같으면서 슈퍼펠린드롬인 문자열을 출력하는 프로그램을 작성하라.
입력 형식
첫 번째 줄에 문자열이 하나 주어진다. 이 문자열의 길이는 $2$ 이상 $100,000$ 이하이며, 이 문자열은 슈퍼펠린드롬이 아니다.
출력 형식
입력으로 주어진 문자열보다 사전순으로 뒤에 있으면서 알파벳 소문자로 이루어져 있고 길이가 같은 문자열들 중에 가장 사전 순으로 빠른 슈퍼펠린드롬을 출력한다.
입력
abaaca
출력
acaaca