젖소의 알파벳
면접 대비시간 제한1초메모리 제한512 MB
26개 문자의 순열과 문자열이 주어질 때, 그 문자열이 반복된 순열의 부분 수열이 되도록 하는 최소 반복 횟수를 구한다.
문제
소에 관한 잘 알려지지 않은 사실이 하나 있다. 소에게는 "카우파벳"이라 불리는 자기들만의 알파벳이 있다. 카우파벳은 'a'부터 'z'까지 26개의 글자로 이루어져 있지만, 소가 카우파벳을 말할 때는 우리에게 익숙한 'abcdefghijklmnopqrstuvwxyz' 순서와 다를 수 있는 특정한 순서로 글자를 나열한다.
시간을 때우기 위해 젖소 Bessie는 카우파벳을 계속해서 흥얼거려 왔고, Farmer John은 그녀가 몇 번이나 흥얼거렸는지 궁금해졌다.
Farmer John이 Bessie가 말하는 것을 들은 소문자 문자열이 주어질 때, Farmer John이 그 문자열을 듣기 위해 Bessie가 카우파벳 전체를 최소 몇 번 흥얼거려야 했는지 구하라. Farmer John은 Bessie가 흥얼거리는 내용에 항상 주의를 기울이지 않기 때문에, Bessie가 흥얼거린 글자 중 일부를 놓쳤을 수 있다. 주어지는 문자열은 그가 들었다고 기억하는 글자들로만 이루어져 있다.
입력
첫째 줄에는 카우파벳에 등장하는 순서대로 26개의 소문자 'a'부터 'z'까지가 주어진다. 다음 줄에는 Farmer John이 Bessie가 말하는 것을 들은 소문자 문자열이 주어진다. 이 문자열의 길이는 이상 이하이다.
출력
Bessie가 카우파벳 전체를 최소 몇 번 흥얼거려야 했는지 출력한다.