/
514C.go
65 lines (56 loc) · 1.09 KB
/
514C.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package main
import (
"bufio"
. "fmt"
"io"
)
// 复杂度 O(|S|√|S|),|S| 为字符串长度之和
// github.com/EndlessCheng/codeforces-go
type node14 struct {
son [3]*node14
end bool
}
func (o *node14) find(s string, miss bool) bool {
if s == "" {
return miss && o.end
}
for i, c := range o.son {
if c != nil && (byte(i) == s[0]-'a' && c.find(s[1:], miss) || !miss && byte(i) != s[0]-'a' && c.find(s[1:], true)) {
return true
}
}
return false
}
type trie14 struct{ root *node14 }
func (t *trie14) put(s string) *node14 {
o := t.root
for i := range s {
b := s[i] - 'a'
if o.son[b] == nil {
o.son[b] = &node14{}
}
o = o.son[b]
}
o.end = true
return o
}
func CF514C(_r io.Reader, _w io.Writer) {
in := bufio.NewReader(_r)
out := bufio.NewWriter(_w)
defer out.Flush()
t := &trie14{&node14{}}
var n, m int
var s string
for Fscan(in, &n, &m); n > 0; n-- {
Fscan(in, &s)
t.put(s)
}
for ; m > 0; m-- {
if Fscan(in, &s); t.root.find(s, false) {
Fprintln(out, "YES")
} else {
Fprintln(out, "NO")
}
}
}
//func main() { CF514C(os.Stdin, os.Stdout) }