레이팅 미적용소에 관한 잘 알려지지 않은 사실 하나는, 소들에게는 그들만의 알파벳인 "소 알파벳(cowphabet)"이 있다는 것이다. 소 알파벳은 'a'부터 'z'까지 26개의 문자로 이루어져 있지만, 소가 소 알파벳을 말할 때는 우리가 익숙하게 듣는 'abcdefghijklmnopqrstuvwxyz' 순서와 다를 수 있는 특정한 순서로 문자들을 나열한다.
시간을 보내기 위해 소 베시는 소 알파벳을 계속해서 반복해 흥얼거리고 있는데, 농부 존은 베시가 그것을 몇 번이나 흥얼거렸는지 궁금하다.
농부 존이 베시에게서 들은 소문자 문자열이 주어질 때, 농부 존이 주어진 문자열을 듣기 위해 베시가 소 알파벳 전체를 흥얼거려야 했던 최소 횟수를 계산하시오. 농부 존은 베시가 흥얼거리는 것에 항상 집중하고 있지는 않아서, 베시가 흥얼거린 문자 중 일부를 놓쳤을 수 있다. 주어지는 문자열은 그가 들었다고 기억하는 문자들만으로 이루어져 있다.
문제 제공: Nick Wu
배점
- 테스트 케이스 2-5에서는 소 알파벳이 일반 알파벳과 같다.
- 테스트 케이스 6-10에는 추가 제약이 없다.
문제 제공: Nick Wu
첫째 줄에 소 알파벳에 나타나는 순서대로 'a'부터 'z'까지 26개의 소문자가 주어진다. 다음 줄에는 농부 존이 베시에게서 들은 소문자 문자열이 주어진다. 이 문자열의 길이는 최소 \(1\), 최대 \(1000\)이다.
베시가 소 알파벳 전체를 흥얼거려야 했던 최소 횟수를 출력한다.
abcdefghijklmnopqrstuvwxyz
mood3In this example, the cowphabet is ordered the same as the normal alphabet.
Bessie must have hummed the cowphabet at least three times. It is possible for
Bessie to have only hummed the cowphabet three times, and for Farmer John to
have heard the letters in uppercase as denoted below.
abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Bronze