Kanglish : 인공 언어 분석
시간 제한2초메모리 제한512 MB
각 문장을 가장 긴 표현을 우선하는 규칙으로 38개 Kan-문자로 나눈 뒤, 인접한 각 쌍을 세어 모든 문자에 대해 가장 자주 뒤따르는 문자와 그 횟수를 Kan 순서로 출력한다.
문제
고(故) 카나자와 교수는 신화를 연구하려고 영어와 비슷한 인공 언어 Kanglish를 만들었다. Kanglish의 단어와 문장은 "Kan 문자"라는 고유한 특수 문자로 적는다. Kan 문자의 집합 크기는 38, 즉 서로 다른 Kan 문자가 38개 있다. Kan 문자는 부호화 문자 집합이 없어 컴퓨터에 직접 저장할 수 없으므로, 카나자와 교수는 각 Kan 문자를 알파벳 한 글자 또는 알파벳 두 글자의 순서 있는 조합으로 나타내는 방법을 고안했다. 따라서 각 Kan 문자는 다음 26개 글자
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
중 하나로, 또는 다음 12개 글자 조합
"ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw", "ts"
중 하나로 나타낸다.
또한 Kan 문자는 위 알파벳 표현에 따라 순서가 정해진다. 이 순서를 Kan 순서라고 하며, "a"로 나타내는 Kan 문자가 첫 번째, "b"로 나타내는 Kan 문자가 두 번째, "z"로 나타내는 Kan 문자가 26번째, "ld"로 나타내는 Kan 문자가 27번째, "ts"로 나타내는 Kan 문자가 38번째(마지막)이다.
Kanglish 단어의 표현은 공백으로 구분한다. 각 문장은 한 줄에 적으므로 Kanglish에는 마침표가 없다. 모든 알파벳 글자는 소문자, 즉 대문자는 없다.
현재 알파벳 표현으로 적힌 Kanglish 문서가 많이 있다. 그러나 카나자와 교수가 번역 방법을 연구한 자료는 대부분 잃어버렸다. 그의 업적을 기리기 위해 우리는 먼저 이 문서를 통계적으로 분석하기로 했다. 첫 번째 분석은 단어에서 연속한 Kan 문자 쌍을 조사하는 것이다.
예를 들어 단어 "quice"의 부분 문자열 "ic"는 "i"와 "c"로 나타내는 두 Kan 문자가 인접한 순서쌍을 뜻한다. 편의상 단어의 알파벳 표현에서 Kan 문자는 왼쪽에서 오른쪽으로 가능한 한 길게 인식한다는 규칙을 둔다. 따라서 부분 문자열 "ncw"는 "nc"와 "w"의 쌍으로 본다. "n"과 "cw"의 쌍도, "n", "c", "w"도 아니다.
각 Kan 문자마다 그 문자와 다른 Kan 문자가 이루는 38가지 쌍이 있다. 예를 들어 "aa", "ab", ..., "az", "ald", ..., "ats"이다. 따라서 수학적으로는 "n"과 "cw"처럼 위 규칙상 실제로는 허용되지 않는 쌍까지 포함해 모두 1444(38x38)가지 쌍이 있다.
여러분의 일은 입력 데이터에서 각 쌍이 몇 번 나타나는지 세는 프로그램을 작성하는 것이다. 예를 들어 문장
qua ist qda quang quice
에서 "qu"로 나타내는 Kan 문자는 세 번 나타난다. "qu"와 "a"의 쌍이 두 번, "qu"와 "i"의 쌍이 한 번 나타난다. 예시 문장에서 알파벳 글자 "q"는 네 번 나타나지만 "qu"가 "q"로 나타내는 Kan 문자와 다른 Kan 문자를 나타내므로 "q"로 나타내는 Kan 문자는 한 번만 나타난다.
편의상 줄 끝의 줄바꿈은 공백으로 본다. 따라서 위 예에서 "e" 다음에는 공백이 온다.
입력
n
line1
line2
...
linen
입력의 첫 줄은 정수 n이며, 뒤따르는 줄의 수를 나타낸다. 첫 줄을 제외한 각 줄은 Kanglish 문장 하나를 나타낸다. n <= 1000이고 각 줄은 공백을 포함해 알파벳 글자가 많아야 59개라고 가정할 수 있다.
출력
a kc1 m1
b kc2 m2
c kc3 m3
...
ts kc38 m38
출력은 입력 전체에 대해 38줄로 이루어진다. 출력의 각 줄은 문자열 두 개와 정수 하나를 가진다. 출력의 i번째 줄에서 첫 번째 문자열은 Kan 순서로 i번째 Kan 문자의 알파벳 표현이다. 예를 들어 첫 줄의 첫 번째 문자열은 "a", 셋째 줄의 첫 번째 문자열은 "c", 37번째 줄의 첫 번째 문자열은 "cw"이다. 첫 번째 문자열 뒤에는 공백이 온다.
i번째 줄의 두 번째 문자열(위에서 kci로 표기)은 첫 번째 Kan 문자 바로 다음에 가장 자주 나타난 Kan 문자의 알파벳 표현이다. 그러한 Kan 문자가 둘 이상이면 Kan 순서로 가장 앞선 것을 출력한다. 두 번째 문자열 뒤에는 공백이 온다.
i번째 줄의 정수(위에서 mi로 표기)는 두 번째 Kan 문자가 첫 번째 Kan 문자 바로 다음에 나타난 횟수이다. 즉 이 정수는 "첫 번째 Kan 문자와 두 번째 Kan 문자의 순서쌍"이 입력에서 나타난 횟수이다. 정수 뒤에는 줄바꿈이 온다.
28번째 출력 줄이 다음과 같다고 하자.
mb e 4
"mb"는 Kanglish 알파벳의 28번째 문자이므로 출력된다. "e 4"는 "mbe" 쌍이 입력에서 4번 나타났고, "mb"로 시작하는 쌍 중에 4번보다 많이 나타난 쌍이 없음을 뜻한다.
i번째 Kan 문자가 입력에 나타나지 않거나, i번째 Kan 문자가 다른 Kan 문자 없이 공백만 뒤따르면 i번째 출력 줄의 두 번째 문자열은 "a"이고 세 번째 항목은 0이어야 한다.
출력에는 공백이 들어가지 않지만, 사이에 공백이 있는 Kan 문자는 쌍으로 보지 않는다. 따라서 다음 예에서
abc def
"d"는 "c" 뒤에 나타난 것으로 세지 않는다.