diff options
author | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2016-11-07 21:35:40 +0700 |
---|---|---|
committer | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2016-11-07 21:35:40 +0700 |
commit | 90eb5475115ecf6725f028ec3c39fab95afcb458 (patch) | |
tree | 1567f90c5bea4e0c247c228b472268d1adfef93d /others/dict/dict.c | |
parent | 1f06cc322606e86918fefa1f707b54264e9ce0a9 (diff) | |
download | cp-90eb5475115ecf6725f028ec3c39fab95afcb458.tar.gz |
others/dict: Optimize dict.py and add dict.c
Diffstat (limited to 'others/dict/dict.c')
-rw-r--r-- | others/dict/dict.c | 53 |
1 files changed, 53 insertions, 0 deletions
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; +} |