Question
The Tale of the Hidden Spell
In a mystical land of letters, there lived a scribe who possessed a long string of magical symbols called s.
The scribe had a secret target spell, t, that needed to be formed from s.
The magic scrolls had a simple rule:
-
You can remove symbols from s, but you cannot rearrange them.
-
The symbols you keep, in order, form a subsequence.
Your task as the apprentice is to:
Count how many distinct ways the scribe can select symbols from s to exactly form the spell t.
Input
The first line of the input contains the string s.
The second line of the input contains the string t.
The second line of the input contains the string t.
Output
Print the number of distinct ways the scribe can select symbols from s to exactly form the spell t.
Example
Input:
rabbbit
rabbit
Output:
3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from "rabbbit".
rabbbit
rabbbit
rabbbit
rabbbit
rabbit
Output:
3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from "rabbbit".
rabbbit
rabbbit
rabbbit