Bài tập | NEU OJ

Một bảng định tuyến (routing table) gồm $n$ tuyến đường (route), mỗi tuyến có dạng:

CIDR NEXT_HOP

trong đó CIDR là A.B.C.D/p và NEXT_HOP là tên trạm kế tiếp (một chuỗi không chứa khoảng trắng).

Với mỗi địa chỉ IP đích cần tra cứu, router chọn tuyến đường phù hợp theo nguyên tắc Longest Prefix Match: trong số tất cả các tuyến mà địa chỉ IP thuộc về (tức IP & mask(p) == network(CIDR)), chọn tuyến có $p$ lớn nhất (tiền tố dài nhất, cụ thể nhất). Đề bài đảm bảo không có hai tuyến nào trùng nhau về cặp (network, prefix), nên luôn có duy nhất một tuyến $p$ lớn nhất khi có khớp.

Nếu không có tuyến nào khớp, in ra NO ROUTE.

Ví dụ:

Input:

4
0.0.0.0/0 ISP1
10.0.0.0/8 R1
10.1.0.0/16 R2
10.1.2.0/24 R3
3
10.1.2.5
10.1.5.5
192.168.1.1

Output:

R3
R2
ISP1

(10.1.2.5 khớp cả 4 tuyến nhưng 10.1.2.0/24 cụ thể nhất nên chọn R3. 192.168.1.1 chỉ khớp tuyến mặc định 0.0.0.0/0 nên chọn ISP1.)

Định dạng đầu vào:
Dòng đầu là số nguyên $n$ ( $1 \le n \le 1000$ ) — số tuyến đường.

$n$ dòng tiếp theo, mỗi dòng dạng CIDR NEXT_HOP.

Dòng tiếp theo là số nguyên $m$ ( $1 \le m \le 1000$ ) — số địa chỉ IP cần tra cứu.

$m$ dòng tiếp theo, mỗi dòng một địa chỉ IPv4 hợp lệ.
Định dạng đầu ra:
In ra $m$ dòng, mỗi dòng là NEXT_HOP của tuyến khớp tốt nhất (tiền tố dài nhất), hoặc NO ROUTE nếu không có tuyến nào khớp.

solution

Đề bài: [An toàn thông tin] Tra cứu định tuyến theo tiền tố dài nhất (Longest Prefix Match)