solution

Trong thực tế, bảng ký hiệu của trình biên dịch thường được cài đặt bằng bảng băm (hash table) để tra cứu nhanh. Bài này yêu cầu bạn từ-vựng-hoá mã nguồn để lấy ra các định danh, tính giá trị băm của từng định danh, rồi đếm số cặp định danh bị đụng độ (cùng giá trị băm).

Cho kích thước bảng băm $M$ và một đoạn mã nguồn nhiều dòng. Token hoá đơn giản: một định danh là dãy ký tự khớp mẫu $[a\text{-}zA\text{-}Z\_][a\text{-}zA\text{-}Z0\text{-}9\_]^*$ (theo maximal munch); mọi ký tự khác trong mã nguồn được bỏ qua hoàn toàn (không có khái niệm từ khoá trong bài này — mọi định danh hợp lệ đều được xét, kể cả khi trùng với từ khoá của ngôn ngữ khác).

Lấy danh sách các định danh duy nhất theo thứ tự xuất hiện lần đầu tiên trong mã nguồn (đọc từ trên xuống dưới, trái sang phải). Với một định danh $s = s_0 s_1 \ldots s_{L-1}$ (dãy ký tự theo đúng thứ tự trong từ), giá trị băm được tính theo công thức đa thức (polynomial rolling hash) cơ số $131$:

$h(s) = \left(\sum_{k=0}^{L-1} \text{ord}(s_k) \cdot 131^{k}\right) \bmod M$

trong đó $\text{ord}(c)$ là mã ASCII của ký tự $c$, và số mũ $k$ tăng dần theo vị trí ký tự tính từ đầu từ (vị trí đầu tiên có $k = 0$).

Sau khi tính băm cho tất cả định danh duy nhất, hãy đếm số cặp $(i, j)$ với $i < j$ (theo chỉ số trong danh sách định danh duy nhất) mà $h(s_i) = h(s_j)$ — đó chính là số cặp đụng độ.