In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of October 26th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #03 exercise sheet]
Little Susan has a new hobby: she likes to remove letters from a word to get another word. It's complicated for her, though, and her brother James always wants to help her.
James gives Susan a word A so that she can reach the word B from it. Susan removes the letters from A in a certain order which is indicated by a permutation P of the indices of the word A. For example, if the word A="SUSAN" and the permutation P={4,1,3,2,5}, then Susan's letter removals make the following sequence of words:
SUSAN → SUSAN → SUSAN → SUSAN → SUSAN → SUSAN
James knows the permutation Susan is going to use. His goal is to stop his sister at some stage and continue to remove the letters himself until he reaches the B word. However, as Susan likes this hobby so much, he wants to stop his sister as late as possible. Your task is to determine how many letters can Susan remove until she James nees to stop her.
Given two strings A and B and a permutation P indicating the order in which Susan is going to remove the letters from A, your task is to compute how many letters can Susan remove such that from the remaining ones James can still obtain word B by removing zero or more letters.
The first line of the input contains the word A. The second line contains the word B. The third line contains a permutation of the valid indexes of A (i.e., a sequence of |A| distinct integers, in the range 1 to |A|). The words will always be sequences of lower case letters and it is guaranteed that it always be possible to obtain B from A.
The output should consist of a single line containing the maximum number of letters that Susan can remove in the order given by the permutation so that from the remaining string James can still obtain the word B by eventually removing more letters, as previously explained before.
The following limits are guaranteed in all the test cases that will be given to your program:
1 ≤ |B| ≤ |A| ≤ 105 | Size of the words | |
1 ≤ Pi ≤ |A| | Integers in the permutation |
Example Input 1 | Example Output 1 |
ababcba abb 5 3 4 1 7 6 2 |
3 |
We have the sequence
ababcba
→
ababcba
→
ababcba
→
ababcba
Susan cannot continue from here since we could not obtain abb from
ababcba
Example Input 2 | Example Output 2 |
bbbabb bb 1 6 3 4 2 5 |
4 |
We have the sequence
bbbabb
→
bbbabb
→
bbbabb
→
bbbabb
→
bbbabb
Susan cannot continue from here since we could not obtain bb from
bbbabb