diff options
Diffstat (limited to 'others/dict')
-rw-r--r-- | others/dict/README.md | 53 | ||||
-rw-r--r-- | others/dict/dict.c | 53 | ||||
-rwxr-xr-x | others/dict/dict.py | 17 |
3 files changed, 0 insertions, 123 deletions
diff --git a/others/dict/README.md b/others/dict/README.md deleted file mode 100644 index 50ff841..0000000 --- a/others/dict/README.md +++ /dev/null @@ -1,53 +0,0 @@ -# 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.c b/others/dict/dict.c deleted file mode 100644 index 9821828..0000000 --- a/others/dict/dict.c +++ /dev/null @@ -1,53 +0,0 @@ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -int cmpstr(const void *s1, const void *s2) -{ - return strcmp((char *) s1, (char *) s2); -} - -short bistr(char (*a)[21], char *x, short hi) -{ - short lo = 0, mid; - - while (lo < hi) { - mid = (lo + hi) / 2; - if (strcmp(a[mid], x) < 0) - lo = mid + 1; - else - hi = mid; - } - - return lo; -} - -int main() -{ - FILE *fi = fopen("dict.inp", "r"), *fo = fopen("dict.out", "w"); - short n, q, i, idx, count; - char (*words)[21], s[21]; - - fscanf(fi, "%hd", &n); - - words = malloc(n * 21); - for (i = 0; i < n; i++) - fscanf(fi, "%s", words[i]); - qsort(words, n, 21, cmpstr); - - fscanf(fi, "%hd", &q); - - for (i = 0; i < q; i++) { - fscanf(fi, "%s", s); - idx = bistr(words, s, n); - count = idx; - while (count < n && !strncmp(words[count], s, strlen(s))) - count++; - fprintf(fo, "%hd\n", count - idx); - } - - fclose(fi); - fclose(fo); - - return 0; -} diff --git a/others/dict/dict.py b/others/dict/dict.py deleted file mode 100755 index 76b8414..0000000 --- a/others/dict/dict.py +++ /dev/null @@ -1,17 +0,0 @@ -#!/usr/bin/env python3 - -from itertools import islice -from bisect import bisect_left as bisect - - -with open('dict.inp') as fi, open('dict.out', 'w') as fo: - words = list(islice(fi, int(fi.readline()))) - words.sort() - - 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)) |