Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Bảng băm ký hiệu với dò tuyến tính (linear probing)

    Cài đặt bảng ký hiệu bằng bảng băm kích thước mmm (các chỉ số slot từ 000 đến m−1m-1m−1), sử dụng hàm băm đa thức cơ số 31:

    h(name)=(∑i=0L−1ord(name[i])⋅31i) mod mh(\text{name}) = \Big(\sum_{i=0}^{L-1} \text{ord}(\text{name}[i]) \cdot 31^{i}\Big) \bmod mh(name)=(∑i=0L−1​ord(name[i])⋅31i)modm

    trong đó name[i] là ký tự thứ iii (0-based, tính từ trái) của tên biến, ord\text{ord}ord là mã ASCII, và LLL là độ dài tên.

    Chèn lần lượt nnn tên biến theo thứ tự cho trước, dùng dò tuyến tính (linear probing): xét lần lượt các slot h(name)h(\text{name})h(name), h(name)+1h(\text{name})+1h(name)+1, h(name)+2h(\text{name})+2h(name)+2, ... (theo modulo mmm, quay vòng) cho tới khi:

    • gặp một slot trống → đặt tên vào slot đó (chèn thành công);
    • hoặc gặp một slot đã chứa đúng tên đang chèn → đây là khai báo trùng, dừng ngay, không chèn gì thêm (coi là DUPLICATE).

    Định nghĩa số bước dò (probe count) của một lần chèn là tổng số slot đã kiểm tra, tính cả slot cuối cùng (nơi đặt vào hoặc nơi phát hiện trùng). Ví dụ nếu chèn thành công ngay tại slot đầu tiên h(name)h(\text{name})h(name) (trống), probe count =1=1=1.

    Giả thiết mmm luôn đủ lớn để bảng không bao giờ đầy trước khi hoàn tất nnn lần chèn (không cần xử lý trường hợp bảng đầy — dữ liệu vào luôn đảm bảo điều này).

    Ví dụ: n=3,m=5n=3, m=5n=3,m=5, các tên ab, ba, ab. Ta có h(ab)=97+98⋅31=3135 mod 5=0h(\text{ab}) = 97 + 98\cdot31 = 3135 \bmod 5 = 0h(ab)=97+98⋅31=3135mod5=0: slot 0 trống → đặt, probes=1. h(ba)=98+97⋅31=3105 mod 5=0h(\text{ba}) = 98 + 97\cdot31 = 3105 \bmod 5 = 0h(ba)=98+97⋅31=3105mod5=0: slot 0 đã bị ab chiếm (khác tên) → thử slot 1, trống → đặt, probes=2. Tên ab thứ hai: slot 0 chứa đúng ab → DUPLICATE, probes=1.

    • Định dạng đầu vào:

      Dòng đầu tiên chứa hai số nguyên n m (1≤n≤20001 \le n \le 20001≤n≤2000, 1≤m≤100071 \le m \le 100071≤m≤10007). nnn dòng tiếp theo, mỗi dòng là một tên biến (chuỗi chữ cái hoa/thường, chữ số, dấu gạch dưới, độ dài 1..301..301..30, không bắt đầu bằng chữ số).

    • Định dạng đầu ra:

      In nnn dòng, dòng thứ iii ứng với tên thứ iii trong input:

      • Nếu chèn thành công vào slot sss với ppp bước dò: in name SLOT s PROBES p.
      • Nếu phát hiện trùng sau ppp bước dò: in name DUPLICATE PROBES p.

      Ví dụ với input nêu trên, output là:

      ab SLOT 0 PROBES 1
ba SLOT 1 PROBES 2
ab DUPLICATE PROBES 1

    Ví dụ:

    Đầu vào:

    1 1
solo

    Đầu ra:

    solo SLOT 0 PROBES 1

    Đầu vào:

    3 5
ab
ba
ab

    Đầu ra:

    ab SLOT 0 PROBES 1
ba SLOT 1 PROBES 2
ab DUPLICATE PROBES 1

    Đang tải editor...