How does this python solution pass for 402 Div-2 D

Revision en1, by pranet, 2017-02-26 19:52:08

25044141 779D - String Game

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

Tags #python, unable to understand

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English pranet 2017-02-26 19:52:08 797 Initial revision (published)