Uddered but not Herd (Bronze)#11195

Uddered but not Herd (Bronze) (Editorial)

Let $a l p h$ contain the alphabet, and let $s$ contain the string that Farmer John heard. We'll process the characters of string $s$ sequentially, finding each current character in the alphabet $a l p h$ . We move through the alphabet from left to right, starting a new pass from its beginning whenever the required letter appears to the left of the previous letter.

Example

In this example, the $co w p hab e t$ cowphabet is ordered the same way as the regular alphabet. Bessie must mumble the $co w p hab e t$ cowphabet at least $3$ times. Below, the way Bessie mumbled is shown, with uppercase letters indicating the letters that Farmer John heard.

Algorithm implementation

Read the alphabet $a l p h$ and the string $s$ .

cin >> alph;
cin >> s;

Keep track of the number of passes through the alphabet using the variable $c n t$ .

cnt = 0;

Use the variable $i$ to iterate through the characters of the string $s$ sequentially.

for (i = 0; i < s.size(); )
{

Use the variable $j$ to iterate through the letters of the alphabet. As soon as we find the next required letter $s [i]$ in the alphabet, increment $i$ by $1$ .

  for (j = 0; j < alph.size(); j++)
    if (s[i] == alph[j]) i++;
  cnt++;
}

Print the answer.

cout << cnt << endl;