From 90eb5475115ecf6725f028ec3c39fab95afcb458 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Mon, 7 Nov 2016 21:35:40 +0700
Subject: others/dict: Optimize dict.py and add dict.c

---
 others/dict/dict.c  | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 others/dict/dict.py | 10 +++-------
 2 files changed, 56 insertions(+), 7 deletions(-)
 create mode 100644 others/dict/dict.c

(limited to 'others/dict')

diff --git a/others/dict/dict.c b/others/dict/dict.c
new file mode 100644
index 0000000..9821828
--- /dev/null
+++ b/others/dict/dict.c
@@ -0,0 +1,53 @@
+#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
index 59724cd..76b8414 100755
--- a/others/dict/dict.py
+++ b/others/dict/dict.py
@@ -1,16 +1,12 @@
 #!/usr/bin/env python3
 
+from itertools import islice
 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)
+    words = list(islice(fi, int(fi.readline())))
+    words.sort()
 
     for _ in range(int(fi.readline())):
         s = fi.readline().strip()
-- 
cgit 1.4.1