平板做网站服务器,呼和浩特网站建设哪家好,2002年做网站多少钱,安卓软件开发公司AcWing 835. Trie 字符串统计
题目描述
维护一个字符串集合#xff0c;支持两种操作#xff1a;
I x 向集合中插入一个字符串 #x1d465;#xff1b;Q x 询问一个字符串在集合中出现了多少次。
共有 #x1d441; 个操作#xff0c;所有输入的字符串总长度不超过 1…AcWing 835. Trie 字符串统计
题目描述
维护一个字符串集合支持两种操作
I x 向集合中插入一个字符串 Q x 询问一个字符串在集合中出现了多少次。
共有 个操作所有输入的字符串总长度不超过 10^5字符串仅包含小写英文字母。
输入格式
第一行包含整数 表示操作数。
接下来 行每行包含一个操作指令指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x都要输出一个整数作为结果表示 在集合中出现的次数。
每个结果占一行。
数据范围
1≤≤2∗10^4
输入样例
5
I abc
Q abc
Q ab
I ab
Q ab输出样例
1
0
1C
#include iostream
#include stringusing namespace std;const int MAX_NODES 100010; // 定义最大节点数int trie[MAX_NODES][26], count[MAX_NODES], index; // trie数组用于存储字典树count数组用于计数index用于记录节点数量// 插入单词到字典树中
void insert(const string word) {int node 0; // 从根节点开始for (char letter: word) { // 遍历单词中的每个字母int idx letter - a; // 将字母映射到[0, 25]的范围内if (!trie[node][idx]) trie[node][idx] index; // 如果当前节点的子节点不存在则创建新的节点node trie[node][idx]; // 移动到下一个节点}count[node]; // 单词插入完成对应节点的计数加一
}// 查询字典树中某个单词的出现次数
int query(const string word) {int node 0; // 从根节点开始for (char letter: word) { // 遍历单词中的每个字母int idx letter - a; // 将字母映射到[0, 25]的范围内if (!trie[node][idx]) return 0; // 如果当前节点的子节点不存在则说明单词不存在于字典树中返回0node trie[node][idx]; // 移动到下一个节点}return count[node]; // 返回单词对应节点的计数值
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;while (n--) {char op;string word;cin op word;if (op I) insert(word);else cout query(word) endl;}return 0;
}Go
package mainimport (bufiofmtos
)const (AlphabetSize 26MaxNodes 100010
)var (trie [MaxNodes][AlphabetSize]intcount [MaxNodes]intindex int
)// 插入单词到字典树中
func insert(word string) {node : 0 // 从根节点开始for i : 0; i len(word); i { // 遍历单词中的每个字母letter : word[i]idx : letter - a // 将字母映射到[0, 25]的范围内if trie[node][idx] 0 { // 如果当前节点的子节点不存在则创建新的节点indextrie[node][idx] index}node trie[node][idx] // 移动到下一个节点}count[node] // 单词插入完成对应节点的计数加一
}// 查询字典树中某个单词的出现次数
func query(word string) int {node : 0 // 从根节点开始for i : 0; i len(word); i { // 遍历单词中的每个字母letter : word[i]idx : letter - a // 将字母映射到[0, 25]的范围内if trie[node][idx] 0 { // 如果当前节点的子节点不存在则说明单词不存在于字典树中return 0}node trie[node][idx] // 移动到下一个节点}return count[node] // 返回单词对应节点的计数值
}func main() {reader : bufio.NewReader(os.Stdin)writer : bufio.NewWriter(os.Stdout)defer writer.Flush()var n intfmt.Fscanln(reader, n)for i : 0; i n; i {var op bytevar word stringfmt.Fscanf(reader, %c %s\n, op, word)if op I {insert(word)} else {fmt.Fprintln(writer, query(word))}}
}模板
int son[N][26], cnt[N], idx;
// 0号点既是根节点又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
void insert(char *str)
{int p 0;for (int i 0; str[i]; i ){int u str[i] - a;if (!son[p][u]) son[p][u] idx;p son[p][u];}cnt[p] ;
}// 查询字符串出现的次数
int query(char *str)
{int p 0;for (int i 0; str[i]; i ){int u str[i] - a;if (!son[p][u]) return 0;p son[p][u];}return cnt[p];
}
