P9940 [USACO21JAN] Uddered but not Herd B

A little-known fact is that cows have their own writing system: “cow language”. Cow language has $26$ letters from `a` to `z`, but when a cow speaks cow language, the order may be different from the `abcdefghijklmnopqrstuvwxyz` we are familiar with; she may arrange the letters in some specific order. To pass the time, the cow Bessie keeps humming the cow-language alphabet song over and over, and Farmer John is curious how many times she has sung it. Given a string of lowercase letters, representing the letters Farmer John heard Bessie sing, compute the minimum number of complete cow-language alphabet songs Bessie must have sung so that Farmer John could have heard the given string. Farmer John is not always paying attention to what Bessie sings, so he may miss some letters that Bessie sang. The given string contains only the letters he remembers hearing.

The first line contains $26$ lowercase letters `a` to `z`, giving the order of the cow-language alphabet. The next line contains a string of lowercase letters, representing the letters Farmer John heard Bessie sing. The length of the string is at least $1$ and at most $1000$.

Output the minimum number of times Bessie sang the complete cow-language alphabet song.

### Sample Explanation 1 In this sample, the cow-language alphabet is in the same order as the usual alphabet. Bessie sang the cow-language alphabet song at least three times. It is possible that Bessie sang it only three times, and Farmer John heard the following letters, which are marked in uppercase. `abcdefghijklMnOpqrstuvwxyz` `abcdefghijklmnOpqrstuvwxyz` `abcDefghijklmnopqrstuvwxyz` ### Test Point Properties - In test points $2-5$, the cow-language alphabet is the same as the usual alphabet. - In test points $6-10$, there are no additional constraints. Translated by ChatGPT 5