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 định danh với nối chuỗi

    Trình biên dịch thường lưu bảng ký hiệu dưới dạng bảng băm (hash table) để tra cứu nhanh. Xét một bảng băm gồm mmm ngăn (bucket), đánh số từ 000 đến m−1m-1m−1, giải quyết đụng độ bằng nối chuỗi (separate chaining). Hàm băm của một định danh (tên) s được định nghĩa là: hash(s)=(∑c∈sord(c)) mod mhash(s) = \left( \sum_{c \in s} \text{ord}(c) \right) \bmod mhash(s)=(∑c∈s​ord(c))modm trong đó ord(c)\text{ord}(c)ord(c) là mã ASCII của ký tự c.

    Bảng nhận vào nnn lệnh, mỗi lệnh thuộc 1 trong 2 dạng:

    • insert <name>: nếu name đã có mặt trong bảng (bất kể ở ngăn nào, do trước đó đã insert thành công), in ra DUPLICATE; ngược lại, thêm name vào cuối danh sách liên kết của ngăn hash(name)hash(name)hash(name) và in ra OK <bucket> (với <bucket> là chỉ số ngăn đó).
    • find <name>: tính bucket = hash(name), duyệt danh sách liên kết của ngăn đó theo đúng thứ tự đã thêm vào; nếu tìm thấy name, in FOUND <bucket> <pos> với <pos> là vị trí của nó trong danh sách (đánh số từ 0); nếu không thấy, in NOTFOUND <bucket>.

    Sau khi xử lý xong toàn bộ nnn lệnh, in thêm đúng mmm dòng mô tả trạng thái cuối cùng của bảng: dòng thứ iii (đánh số từ 000 đến m−1m-1m−1) liệt kê nội dung ngăn iii — các tên trong danh sách liên kết theo đúng thứ tự đã thêm, cách nhau bởi dấu phẩy , (không có khoảng trắng); nếu ngăn rỗng, in dấu gạch ngang -.

    Ví dụ (m=3,n=4m=3, n=4m=3,n=4):

    insert ab
insert bc
find ab
insert ab

    Kết quả:

    OK 0
OK 2
FOUND 0 0
DUPLICATE
ab
-
bc
    • Định dạng đầu vào:

      Dòng đầu: hai số nguyên mmm và nnn (1≤m≤1001 \le m \le 1001≤m≤100, 0≤n≤20000 \le n \le 20000≤n≤2000), cách nhau bởi khoảng trắng. nnn dòng tiếp theo, mỗi dòng insert <name> hoặc find <name>, name gồm chữ cái thường (độ dài từ 1 đến 20).

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

      nnn dòng đầu là kết quả của từng lệnh theo đúng thứ tự xử lý. mmm dòng tiếp theo mô tả nội dung các ngăn theo chỉ số tăng dần từ 0 đến m−1m-1m−1, mỗi ngăn một dòng.

    Ví dụ:

    Đầu vào:

    1 0

    Đầu ra:

    -

    Đầu vào:

    3 4
insert ab
insert bc
find ab
insert ab

    Đầu ra:

    OK 0
OK 2
FOUND 0 0
DUPLICATE
ab
-
bc

    Đang tải editor...