def match(string, trie):
 longest = None
 for i in range(len(string)):
  substr = string[:(i + 1)]
  if (not trie.has_prefix(substr)):
   break
  if (substr in trie):
   longest = substr
 return longest

def match ( string , trie ) : longest = None for i in range ( len ( string ) ) : substr = string [ : ( i + 1 ) ] if ( not trie . has_prefix ( substr ) ) : break if ( substr in trie ) : longest = substr return longest
try to apply the pattern at the start of the string .