KMOP timer 0.5s memory 1024MB

아마 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)를 선택하여 이를 조합한 것이다.

너의 목표는 발음할 수 있는 최소 길이의 약어를 찾는 것이다.

예를 들어, N = 3인 구 “KNUTH MORRIS PRATT”을 생각해보자. 이 구에서는 총 27개의 가능한 약어가 존재한다. 예를 들어

• “KMP”

• “KMPR”

• “KMPRA”

• “KMOP”

• “KMOPR”

• “KNUMORPRA” 등

이 중에서 “KMOP”와 “KMOPR”은 발음할 수 있지만, “KMP”, “KMPR”, “KMPRA”, “KNUMORPRA” 등은 발음할 수 없다.

따라서 최소 길이의 발음할 수 있는 약어는 “KMOP”이며, 길이는 4이다.