멋진 이름 짓기

Claim. $s_i$ 중 최대 점수를 받는 이름이 존재한다.

Proof. 어떤 이름 $t$가 최대 점수 $v$를 받는다고 가정하자. 다음 과정을 반복한다.

• $t$가 $s_i$ 중 어느 것과도 다르다면 마지막 글자를 제거한다.
• $t$와 같은 $s_i$가 존재한다면, 이 과정을 종료한다.

$t$가 $s_i$ 중 어느 것과도 다르다면, $i \in \{1, 2, \dots, n\}$ 중 $s_i$가 $t$의 접두사인 $i$의 집합은 $t$의 마지막 글자를 지워도 변하지 않는다. 따라서, 마지막 글자를 지워도 점수가 변하지 않는다. $t$의 길이가 유한하므로, 위 과정을 반복하다 보면 언젠가는 최대 점수를 가지며 $s_i$ 중 적어도 하나와 같은 문자열에 도달하게 된다.

위 증명에 의해, $n$개의 문자열 $s_i$가 가지는 점수를 모두 계산하고, 그 중 최댓값을 출력하면 된다. 이는 $O(n \sum |s_i|)$ 시간에 쉽게 구현할 수 있다. Trie 등의 자료구조를 사용해 $O(\sum |s_i|)$ 시간으로 최적화하는 것도 가능하지만, 문제를 풀기 위해 요구되는 최적화는 아니다.