LZW 인코딩

문제

문자열을 학교 방식의 LZW로 압축해 사전과 코드를 출력한다.

1. 문자열을 한 번 읽어 처음 나오는 글자마다 1번부터 차례로 번호를 붙여 기본 사전을 만든다.
2. 문자열을 처음부터 다시 읽는다. 현재 문자열 s에 글자 c를 붙인 s + c가 사전에 있으면 s = s + c로 이어 붙인다. 없으면 s의 번호를 코드로 출력하고 s + c를 사전의 다음 번호로 등록한 뒤 s = c로 다시 시작한다.
3. 다 읽고 남은 s의 번호를 마지막 코드로 출력한다.

사전에 있는지는 map의 find로 확인한다. endic[s + c]로 검사하면 없던 키가 생긴다.

제한

문자열의 길이는 1 이상 3000 이하이다.

입출력 예시

입력

ABABBABCABABBA

출력

11
1 A
2 B
3 C
4 AB
5 BA
6 ABB
7 BAB
8 BC
9 CA
10 ABA
11 ABBA
1 2 4 5 2 3 4 6 1