Uzunluğuna görə ən uzun prefiksin uyğunluğu
İnternetdə marşrutlayıcı paketləri təyinat ünvanına görə yönləndirir və bu məqsədlə yönləndirmə cədvəlindən istifadə edir. Bu cədvəl, hər bir təyinat nöqtəsi üçün paketin keçməli olduğu yolu (əgər varsa) müəyyən edir. Təyinat ünvanı 32 bitlik işarəsiz tam ədəddir. Yönləndirmə cədvəlində bir çox müxtəlif prefikslər (minlərlə) mövcuddur və hər biri prefiks (m, l) cütlüyü ilə təmsil olunur. Burada m - ünvan maskası (işarəsiz tam ədəd), l isə maskadakı əhəmiyyətli bitlərin sayını göstərən uzunluqdur. Təyinat ünvanı d prefiksə (m, l) uyğun gəlir, əgər d-nin l ən yüksək bitləri m-in l ən yüksək bitləri ilə üst-üstə düşürsə.
Ən uzun prefiks uyğunluğu: bir məlumat paketi daxil olduqda, marşrutlayıcı təyinat ünvanı ilə uyğun gələn ən uzun prefiksi öz bazasında tapmalıdır. Siz bir neçə milyon paketi emal edən marşrutlayıcı üçün Ən Uzun Prefiks Uyğunluğunu həyata keçirməlisiniz.
Giriş məlumatları
Birinci sətir iki tam ədəd x (x ≤ 10000) və y ehtiva edir. x marşrutlayıcının yönləndirmə cədvəlindəki prefikslərin sayını, y isə ötürülən paketlərin sayını göstərir. Növbəti x sətir prefiksləri təsvir edir: hər bir sətir onaltılıq maska ilə təmsil olunan bir prefiksi (maksimum 32 bit ehtiva edən) və onun uzunluğunu len (0 < len ≤ 32) onluq əsasda göstərir. Hər bir prefiks, göründüyü sətirin nömrəsindən bir çıxmaqla bərabər olan bir rəqəmlə identifikasiya olunur (yəni birinci prefiks id 0, ikinci 1 və s. malikdir). Növbəti y sətir paketlərin çatdırılmalı olduğu təyinat ünvanlarını göstərir, hər sətirdə bir paket (ünvanlar da onaltılıq formatda verilir).
Çıxış məlumatları
y sətir çıxış edin. k-cı giriş ünvanı üçün ən uzun prefiks uyğunluğunun nəticəsini ehtiva edən k-cı sətir. Nəticə ya ən uzun uyğun gələn prefiksin identifikatoru, ya da uyğunluq tapılmadıqda -1 olacaq.