t = raw_input()
p = raw_input()
aa = [int(x) - 1 for x in raw_input().split()]
l = len(p)
r = lt = len(t)
while l < r:
m = (l + r) // 2
sa = set(aa[:lt-m])
it = (a for i, a in enumerate(t) if i not in sa)
if all(c in it for c in p):
r = m
else:
l = m + 1
print(lt - l)
In particular, how does the line
if all(c in it for c in p):
work? How is it able to ensure that p is a subsequence of it by a simple containment check over all the letters of p? I expected it to output 2 (instead of 1, which is the correct answer) for the following case, but it worked correctly.
abab
ab
1 4 3 2
Woah! As far as I know, the in keyword only checks if an object is contained within a sequence or not. You can refer to the internal implementation here.
But, the trick here is that an iterator object is first being created in this code. An iterator yields items that were not yielded in previous iterations. Hence, this works.
This StackOverflow answer might be useful for explanation.
Thanks!