Matching Contacts by Email Domain and Preferences

Problem: Matching Contacts by Email Domain and Preferences You are given a list of contacts. Each contact has: name: the contact's name email: the contact's own email address preferences: an ordered list of customer email domain patterns the contact is willing to handle Given several customer emails, return all matching contacts for each customer email, sorted by matching priority. Matching Rules For a customer email user@domain, extract the domain part domain. For each contact: If the contact's preferences list is non-empty: Match only against the patterns in preferences. If multiple patterns match, use the earliest matching pattern as the contact's priority. If the contact's preferences list is empty: Match using the domain of the contact's own email address exactly. For example, alice@stripe.com matches only stripe.com by default. Wildcard Rules A preference pattern may have one of the following forms: Exact domain: stripe.com matches only stripe.com Wildcard subdomain: *.stripe.com matches api.stripe.com, pay.stripe.com, but not stripe.com Global wildcard: * matches any domain Sorting Rules For each customer email, sort all matching contacts by: Smaller matching priority first. Earlier preference patterns have higher priority. A contact without preferences has default matching priority 0. If priorities are equal, preserve the original input order of contacts. Input Format Read input from stdin. n name|email|preferences name|email|preferences ... q customer_email customer_email ... Where: n is the number of contacts. Each contact line has fields separated by |. preferences is a comma-separated list of domain patterns. If a contact has no preferences, this field is -. q is the number of queries. Output Format For each customer email, print one line: If there are matching contacts, print their names joined by commas ,. Otherwise, print EMPTY. Constraints 1 <= n <= 10^4 1 <= q <= 10^4 Each contact has at most 20 preference patterns Emails and domains contain only lowercase letters, digits, ., -, _, and @ name does not contain | Example Input: 4 Alice|alice@stripe.com|- Bob|bob@example.com|stripe.com,*.stripe.net Carol|carol@foo.com|*.stripe.com,* Dave|dave@stripe.net|- 4 user@stripe.com user@api.stripe.com user@pay.stripe.net user@unknown.org Output: Alice,Bob,Carol Carol Bob,Carol Carol Example Input 4 Alice|alice@stripe.com|- Bob|bob@example.com|stripe.com,*.stripe.net Carol|carol@foo.com|*.stripe.com,* Dave|dave@stripe.net|- 4 user@stripe.com user@api.stripe.com user@pay.stripe.net user@unknown.org Output Alice,Bob,Carol Carol Bob,Carol Carol