今天做一道trie树题目，只要在每个节点维护一个cnt，然后对每个查询的单词把路径上的cnt累加就好

https://www.acwing.com/problem/content/description/144/

go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const (
	ALPHABET_SIZE = 26
)

type TrieNode struct {
	children [ALPHABET_SIZE]*TrieNode
	cnt      int // 记录以该节点为末尾的字符串数量
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{
		root: &TrieNode{},
	}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, char := range word {
		index := char - 'a'
		if node.children[index] == nil {
			node.children[index] = &TrieNode{}
		}
		node = node.children[index]
	}
	node.cnt++ // 每插入一个字符串，末尾节点的 cnt 加1
}

func (t *Trie) CountPrefix(prefix string) int {
	node := t.root
	totalCnt := 0
	for _, char := range prefix {
		index := char - 'a'
		if node.children[index] == nil {
			return totalCnt
		}
		node = node.children[index]
		totalCnt += node.cnt // 累加途径每个节点的 cnt 值
	}
	return totalCnt
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	// 读取 N 和 M
	var N, M int
	fmt.Fscanf(reader, "%d %d\n", &N, &M)

	// 读取 N 个字符串并构建字典树
	trie := NewTrie()
	for i := 0; i < N; i++ {
		var word string
		fmt.Fscanf(reader, "%s\n", &word)
		trie.Insert(word)
	}

	// 处理 M 个查询
	for i := 0; i < M; i++ {
		var query string
		fmt.Fscanf(reader, "%s\n", &query)
		fmt.Println(trie.CountPrefix(query))
	}
}