시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB47211753.125%

문제

길이가 $n$인 문자열 $S=s_1s_2\cdots s_n$와 길이가 $n$인 양의 정수 수열 $A=(a_1, a_2, \cdots a_n)$를 이용하여 다음과 같이 새로운 문자열 $T$를 만들 수 있다.

  • $X_0$는 빈 문자열이다.
  • $X_i = X_{i-1} s_i X_{i-1} s_i \cdots s_i X_{i-1}$, $s_i$는 $a_i$번, $X_{i-1}$은 $a_i + 1$번 등장한다.
  • $T = X_n$이다.

예를 들어 $S=abc$고, $A=(1,2,1)$이면 $X_1=a, X_2=ababa, X_3=T=ababacababa$가 된다.

$S$와 $A$를 이용하여 $T$를 만드는 것은 쉬우니, 반대로 $T$가 주어졌을 때 $T$를 만들어내는 $S$와 $A$를 찾아보자.

입력

문자열 $T$가 주어진다.

출력

첫 번째 줄에 $S$를 출력한다.

두 번째 줄에 $A$를 공백으로 구분하여 출력한다.

정답이 여러 개인 경우 아무 거나 한 가지만 출력한다.

제한

  • $T$의 길이는 1 이상 $2^{20} = 1\,048\,576$ 미만이고, 알파벳 소문자로만 구성되어 있다.
  • 조건을 만족하는 $S$와 $A$가 존재하는 입력만이 주어진다.

예제 입력 1

ababacababa

예제 출력 1

abc
1 2 1

예제 입력 2

ccccccc

예제 출력 2

c
7

$(c, \{7\}), (cc, \{1,3\}), (ccc, \{1,1,1\})$ 등이 모두 정답이다.

출처

University > 제주대학교 > 2021 하반기 취업 알고리즘 집중특강 및 해커톤 대회 F번