지원 요청 입력 기록

문제

사내 IT 지원 창구는 간단한 문자 입력기로 요청 이름을 받는다. 이 입력기는 글자를 추가하거나 지운 기록과 제출 명령을 하나의 문자열에 차례대로 저장한다. 관리자는 이 문자열을 재생하여 실제로 제출된 요청 이름별 횟수를 구하려 한다. 재생을 시작할 때 작성 중인 요청 이름은 빈 문자열이다. 입력 기록은 영문 소문자, 숫자, 그리고 세 특수 문자 #, |, 역슬래시로 이루어진다. 영문 소문자나 숫자를 읽으면 작성 중인 이름의 맨 뒤에 그대로 붙인다. 특수 문자 #을 읽으면 작성 중인 이름의 마지막 문자 하나를 지운다. 이름이 비어 있다면 아무 일도 일어나지 않는다. 지워지는 문자는 종류와 관계없이 마지막 문자 하나다. 특수 문자 |를 읽으면 현재 이름을 제출하고 작성 중인 이름을 빈 문자열로 바꾼다. 다만 현재 이름이 비어 있으면 제출 횟수를 늘리지 않고 빈 상태를 유지한다. 같은 이름을 여러 번 제출할 수 있으며, 그때마다 해당 이름의 제출 횟수가 1씩 늘어난다. 역슬래시를 읽었을 때 뒤에 문자가 남아 있으면 바로 다음 문자 하나를 명령으로 해석하지 않고 이름의 맨 뒤에 붙인다. 이때 다음 문자는 이미 처리한 것으로 보며 다시 해석하지 않는다. 따라서 #, |, 역슬래시 자체도 이름에 포함될 수 있다. 역슬래시가 입력 기록의 마지막 문자라면 역슬래시 자체를 이름의 맨 뒤에 붙인다. 입력 기록을 끝까지 읽은 뒤에는 작성 중인 이름을 한 번 더 제출한다. 이때도 빈 이름은 제출하지 않는다. 제출된 서로 다른 이름의 수와 각 이름의 제출 횟수를 구해야 한다. 이름은 문자 순서가 #, 숫자 0부터 9, |, 역슬래시, 영문 소문자 a부터 z인 사전순으로 정렬한다. 한 이름이 다른 이름의 접두사라면 짧은 이름이 먼저다. 제출된 이름이 없으면 서로 다른 이름의 수를 나타내는 0만 출력한다.

입력

첫째 줄에 입력 기록의 길이 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
둘째 줄에 길이가 정확히 N인 입력 기록 S가 주어진다. S는 영문 소문자 a~z, 숫자 0~9, #, |, 역슬래시로만 이루어지며 공백은 없다.

출력

첫째 줄에 제출된 서로 다른 이름의 수 M을 출력한다. 다음 M개 줄에 이름과 제출 횟수를 공백으로 구분하여 지정한 사전순으로 출력한다. 이름 안의 특수 문자는 역슬래시를 추가하지 않고 그대로 출력한다. M이 0이면 추가 줄을 출력하지 않는다.

20
pc1|pc2#1|net\|a|pc1

2
net|a 1
pc1 3

5
##||#

0

8
\#|a|ab\

3
# 1
a 1
ab\ 1

출처: Devin.KR 자체 제작