From 1f06cc322606e86918fefa1f707b54264e9ce0a9 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Sun, 6 Nov 2016 21:53:13 +0700
Subject: Add others/dict

---
 others/dict/README.md | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++
 others/dict/dict.py   | 21 ++++++++++++++++++++
 2 files changed, 74 insertions(+)
 create mode 100644 others/dict/README.md
 create mode 100755 others/dict/dict.py

(limited to 'others/dict')

diff --git a/others/dict/README.md b/others/dict/README.md
new file mode 100644
index 0000000..50ff841
--- /dev/null
+++ b/others/dict/README.md
@@ -0,0 +1,53 @@
+# Từ điển
+
+Cho một từ điển, là một danh sách gồm `n` từ `w`. Cho `q` truy vấn, mỗi truy vấn đưa ra
+một xâu `s`, yêu cầu đếm xem có bao nhiêu từ có tiền tố là `s`.
+
+## Input
+
+`dict.inp` gồm `n` + `q` + 2 dòng:
+
+* Dòng 1: Gồm một số nguyên là số `n`, số lượng từ của từ điển.
+* Dòng 2 đến `n` + 1: Mỗi dòng gồm một xâu kí tự `w` là một từ thuộc từ điển.
+* Dòng `n` + 2: Gồm một số nguyên là số `q`, số lượng truy vấn.
+* Dòng `n` + 3 đến `n` + `q` + 2: Mỗi dòng gồm một xâu kí tự `s` mô tả một tiền
+  tố cần đếm.
+
+## Output
+
+`dict.out` gồm `q` dòng, mỗi dòng gồm một số nguyên là câu trả lời cho
+truy vấn tương ứng.
+
+## Giới hạn
+
+* 1 ≤ `n`, `q` ≤ 20000.
+* 1 ≤ Độ dài `w`, `s` ≤ 20.
+* Các xâu `w`, `s` gồm các chữ cái in thường (từ `a` đến `z`).
+
+## Ví dụ
+
+`dict.inp`:
+
+    4
+    banana
+    ban
+    baconsoi
+    alibaba
+    4
+    ban
+    ba
+    ali
+    baba
+
+`dict.out`:
+
+    2
+    3
+    1
+    0
+
+Giải thích:
+
+* 2 từ có tiền tố `ban` là: `banana`, `ban`.
+* 3 từ có tiền tố `ba` là: `banana`, `ban`, `baconsoi`.
+* 2 từ có tiền tố `ali` là: `alibaba`.
diff --git a/others/dict/dict.py b/others/dict/dict.py
new file mode 100755
index 0000000..59724cd
--- /dev/null
+++ b/others/dict/dict.py
@@ -0,0 +1,21 @@
+#!/usr/bin/env python3
+
+from bisect import bisect_left as bisect
+
+words = []
+
+
+with open('dict.inp') as fi, open('dict.out', 'w') as fo:
+    for _ in range(int(fi.readline())):
+        w = fi.readline().strip()
+        i = bisect(words, w)
+        if i == len(words) or w != words[i]:
+            words.insert(i, w)
+
+    for _ in range(int(fi.readline())):
+        s = fi.readline().strip()
+        i = bisect(words, s)
+        count = 0
+        while i + count < len(words) and words[i + count].startswith(s):
+            count += 1
+        fo.write("{}\n".format(count))
-- 
cgit 1.4.1