問題
아마 KMP 알고리즘을 알고 있을 것이다. 또한 “KMP”는 1977년에 공동으로 알고리즘을 발표한 “Knuth Morris Pratt”의 약어라는 것도 알고 있을 수 있다. 그렇다면 “KMP”를 어떻게 발음하는가? 물론 “Knuth Morris Pratt”이라고 말할 수도 있지만, 약어 자체를 발음할 수도 있다. 하지만 “KMP”는 발음할 수 있는 단어가 아니므로, 어쩔 수 없이 각 글자를 하나씩 읽어야 한다. 이 문제에서는 발음할 수 있는 약어를 찾는 것이 목표이다.
이를 명확하게 정의하기 위해 몇 가지 개념을 정리하겠다.
• 구(phrase): 단어들의 리스트이다.
• 단어(word): 글자들의 연속된 집합이다.
• 모음(vowel)과 자음(consonant): 모음은 “A”, “E”, “I”, “O”, “U”, “Y”로 정의하고, 나머지는 모두 자음이다.
• 발음할 수 있는 단어(pronounceable word): 연속된 자음이 2개를 초과하여 포함되지 않는 단어이다. 예를 들어, “LEMPEL”은 발음할 수 있지만, “DIJKSTRA”는 그렇지 않다.
주어진 구에서 약어(acronym)는 각 단어에서 최소 1개, 최대 3개의 접두사(prefix)를 선택하여 이를 조합한 것이다.
너의 목표는 발음할 수 있는 최소 길이의 약어를 찾는 것이다.
예를 들어,
• “KMP”
• “KMPR”
• “KMPRA”
• “KMOP”
• “KMOPR”
• “KNUMORPRA” 등
이 중에서 “KMOP”와 “KMOPR”은 발음할 수 있지만, “KMP”, “KMPR”, “KMPRA”, “KNUMORPRA” 등은 발음할 수 없다.
따라서 최소 길이의 발음할 수 있는 약어는 “KMOP”이며, 길이는 4이다.
入力
첫 번째 줄에는 양의 정수
다음
각 단어는 비어 있지 않은 대문자로만 이루어진 문자열이다.
모든 단어의 길이 합은 최대
出力
발음할 수 있는 약어 중 최소 길이를 출력한다.
만약 발음할 수 있는 약어가 존재하지 않으면 *를 출력한다.
例題 #1
3
KNUTH
MORRIS
PRATT
4
例題 #2
3
KNUTH
M
PRATT
5
例題 #3
3
K
M
P
*
例題 #4
2
K
M
2
例題 #5
4
YOU
SHOULD
BE
DANCING
5
ログインしないとコードを書けません。