Longest-Prefix-Match Routing Lookup

Problem Statement

A router forwards a packet using the routing entry with the longest matching prefix. Given a routing table and a destination IP, return the chosen next hop.

Background

Each route is (cidr, next_hop). A route matches if the destination is inside its CIDR. Among all matching routes, the one with the largest prefix length wins (most specific). Ties on prefix length are impossible for distinct non-overlapping routes, but if present, the earliest in the table wins. If no route matches, return "drop". A 0.0.0.0/0 route is the default gateway.

Your Task

def route_lookup(table, dest):

• table: list of (cidr, next_hop).
• Return the next hop string, or "drop".

Input Format

• table (list of (str, str)), dest (str).

Output Format

• A next-hop string or "drop".

Sample

table = [("0.0.0.0/0", "gw"), ("10.0.0.0/8", "r1"), ("10.1.0.0/16", "r2")]
print(route_lookup(table, "10.1.2.3"))

Output:

r2