Uddered but not Herd
면접 대비시간 제한2초메모리 제한512 MB
소 알파벳을 여러 번 반복했을 때 들린 문자열이 부분 수열로 나타나는 최소 반복 횟수를 구합니다.
문제
소에게는 '소 알파벳'(cowphabet)이라는 고유한 알파벳이 있다는 사실은 잘 알려져 있지 않다. 이 알파벳은 'a'부터 'z'까지 26개 글자로 이루어져 있지만, 소가 말할 때는 우리에게 익숙한 'abcdefghijklmnopqrstuvwxyz' 순서와 다른 특정한 순서로 글자를 나열한다.
벳시의 사촌 밀드레드는 소 알파벳을 계속 흥얼거리고 있고, 농부 Nhoj는 그녀가 몇 번이나 흥얼거렸는지 궁금해한다.
농부 Nhoj는 항상 주의 깊게 듣지는 않아서 밀드레드가 흥얼거린 글자 중 일부를 놓쳤을 수 있다. 주어진 문자열은 농부가 들었다고 기억하는 글자로만 이루어져 있다. 농부가 이 문자열을 들을 수 있도록 밀드레드가 소 알파벳 전체를 최소 몇 번 흥얼거렸어야 하는지 구하시오.
입력
입력은 한 줄이며, 농부 Nhoj가 들은 밀드레드의 발언인 소문자 알파벳 문자열이 주어진다. 문자열의 길이는 1 이상 이하이다.
출력
밀드레드가 소 알파벳 전체를 흥얼거린 최소 횟수를 출력한다.
제한
테스트 1~5번에서 농부 Nhoj는 밀드레드 또는 벳시의 이름에 나오는 글자만 들었다.
테스트 6~16번에서 농부 Nhoj는 밀드레드의 이름에 나오는 글자를 한 번도 듣지 못했다.
힌트
밀드레드는 소 알파벳을 최소 세 번 흥얼거렸어야 한다. 소 알파벳이 "mildre"로 시작하고 농부 Nhoj가 아래와 같이 대문자로 표시된 글자를 들었다면, 밀드레드는 세 번만 흥얼거렸을 수 있다.
MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz