others/dict/dict.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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))