题解 | #正则匹配#

package main

import (
    "fmt"
)

type Trie struct {
	son [26]*Trie
	cnt int
}

func (t *Trie) Insert(s string) {
    node := t
    for i := range s {
        c := int(s[i] - 'a')
        if node.son[c] == nil {
            node.son[c] = &Trie{}
        }
        node.son[c].cnt++
        node = node.son[c]
    }
}

func (t *Trie) CountPrefix(s string) int {
    node := t
    for i := range s {
        c := int(s[i] - 'a')
        if node.son[c] == nil {
            return 0
        }
        node = node.son[c]
    }
    return node.cnt
}
func main() {
    var n int
    fmt.Scan(&n)
    t := &Trie{}
    for i := 0; i < n; i++ {
        var s string
        fmt.Scan(&s)
        t.Insert(s)
    }
    var q int
    fmt.Scan(&q)
    for i := 0; i < q; i ++ {
        var s string
        fmt.Scan(&s)
        fmt.Println(t.CountPrefix(s))
    }
}