输入包含多行,第一行一个整数m,代表操作次数。接下来m行,每行包含一个整数op,和一个字符串word。
对于每次操作,如果op为3时,如果word在字典树中,请输出“YES”,否则输出“NO”;如果op为4时,请输出返回以word为前缀的单词数量,其它情况不输出。
7 1 qwer 1 qwe 3 qwer 4 q 2 qwer 3 qwer 4 q
YES 2 NO 1
要求时空复杂度均为
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; class TrieNode { public int pass; public int end; public TrieNode[] nexts; public TrieNode() { pass = 0; end = 0; nexts = new TrieNode[26]; } } class Trie { public TrieNode root; public Trie() { root = new TrieNode(); } public void insert(char[] word) { if(word == null) return; TrieNode node = root; node.pass ++; int offset = 0; for(int i = 0; i < word.length; i++){ offset = word[i] - 'a'; if(node.nexts[offset] == null) node.nexts[offset] = new TrieNode(); node = node.nexts[offset]; node.pass ++; } node.end ++; } public void delete(char[] word) { if(search(word)){ // 加入过才删 TrieNode node = root; int offset = 0; for(int i = 0; i < word.length; i++){ offset = word[i] - 'a'; if(--node.nexts[offset].pass == 0){ // 当前字符直接没有了,后面的节点全部释放掉 node.nexts[offset] = null; return; } node = node.nexts[offset]; } node.end--; } } public boolean search(char[] word) { if(word == null) return false; TrieNode node = root; int offset = 0; for(int i = 0; i < word.length; i++){ offset = word[i] - 'a'; if(node.nexts[offset] == null) return false; node = node.nexts[offset]; } return node.end > 0; } public int prefixNumber(char[] word) { if(word == null) return 0; TrieNode node = root; int offset = 0; for(int i = 0; i < word.length; i++){ offset = word[i] - 'a'; if(node.nexts[offset] == null) return 0; node = node.nexts[offset]; } return node.pass; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); Trie tree = new Trie(); for(int i = 0; i < n; i++){ String[] params = br.readLine().split(" "); if(params[0].equals("1")){ tree.insert(params[1].toCharArray()); }else if(params[0].equals("2")){ tree.delete(params[1].toCharArray()); }else if(params[0].equals("3")){ System.out.println(tree.search(params[1].toCharArray())? "YES": "NO"); }else{ System.out.println(tree.prefixNumber(params[1].toCharArray())); } } } }
#include <stdlib.h> #include <stdbool.h> #include <string.h> #include <stdio.h> typedef struct tn { int pass; int end; struct tn **children; // 存放子节点的指针 } node; node *new_node() { node *new_node = malloc(sizeof(node)); new_node->pass = 0; new_node->end = 0; new_node->children = (node **) calloc(26, sizeof(node *)); return new_node; } void destroy_node(node *node) { free(node->children); free(node); } void destroy_whole_path(node *node) { for (int i = 0; i < 26; i++) { if (node->children[i] != NULL) { destroy_node(node->children[i]); } } destroy_node(node); } typedef node *trie; trie new_trie() { return new_node(); } void insert(trie trie, char *word) { if (word == NULL || strlen(word) == 0) { return; } int len = (int) strlen(word); node *cur = trie; cur->pass++; int path; for (int i = 0; i < len; i++) { path = word[i] - 'a'; if (cur->children[path] == NULL) { cur->children[path] = new_node(); } cur = cur->children[path]; cur->pass++; } cur->end++; } bool search(trie trie, char *word) { if (word == NULL || strlen(word) == 0) { return false; } node *cur = trie; int path; for (int i = 0; i < strlen(word); i++) { path = word[i] - 'a'; if (cur->children[path] == NULL) { return false; } cur = cur->children[path]; } return cur->end != 0; } void delete(trie trie, char *word) { if (!search(trie, word)) { return; } node *cur = trie, *next; cur->pass--; int path; for (int i = 0; i < strlen(word); i++) { path = word[i] - 'a'; if (--cur->children[path]->pass == 0) { next = cur->children[path]; cur->children[path] = NULL; destroy_whole_path(next); return; } cur = cur->children[path]; } cur->end--; } int prefixNumber(trie trie, char *word) { if (word == NULL || strlen(word) == 0) { return false; } node *cur = trie; int path; for (int i = 0; i < strlen(word); i++) { path = word[i] - 'a'; if (cur->children[path] == NULL) { return 0; } cur = cur->children[path]; } return cur->pass; } #define MAXLEN 21 int main(void) { trie trie = new_trie(); int n, op; char str[MAXLEN]; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%s", &op, str); if (op == 1) insert(trie, str); else if (op == 2) delete(trie, str); else if (op == 3) printf("%s\n", search(trie, str) ? "YES" : "NO"); else if (op == 4) printf("%d\n", prefixNumber(trie, str)); } destroy_node(trie); return 0; }
#include<bits/stdc++.h> using namespace std; const int N = 1e6+10; // 结点总出现数 int cnt; // 当前结点(第几个结点) int Tree[N][26]; // 结点路径记录表 int pass[N]; // 该结点的通过数 int endd[N]; // 该结点作为末尾数 // 单词插入: void word_insert(string word) { int tool=1; // 遍历工具 - 从第 1 个结点开始 int path=0; // 路径记录 pass[tool]++; // 第一个结点通过数++ // 遍历单词 从第二个结点开始记录 for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母 { path = c - 'a'; // 第 1 & 2 结点之间的路径 // 没有该结点: if(Tree[tool][path]==0) { // 添加结点: Tree[tool][path] = ++cnt; // 遍历工具访问下一结点,结点通过数++ tool = Tree[tool][path]; pass[tool]++; } // 有对应结点: else { // 遍历工具访问下一结点,结点通过数++ tool = Tree[tool][path]; pass[tool]++; } } // 结点作为末尾数++ endd[tool]++; return; } // 单词查重: int word_duplicate(string word) { int tool=1; // 遍历工具 - 从第 1 个结点开始 int path=0; // 路径记录 // 遍历单词 从第二个结点开始记录 for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母 { path = c - 'a'; // 第 1 & 2 结点之间的路径 // 没有该结点: if(Tree[tool][path]==0) { return 0; } // 有对应结点: else { // 遍历工具访问下一结点,结点通过数++ tool = Tree[tool][path]; } } // 返回结点作为末尾数: return endd[tool]; } void word_delete(string word) { // 没有该单词 if(!word_duplicate(word)) { return; } // 有该单词: else { int tool=1; // 遍历工具 - 从第 1 个结点开始 int path=0; // 路径记录 pass[tool]--; // 第一个结点通过数++ // 遍历单词 从第二个结点开始记录 for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母 { path = c - 'a'; // 第 1 & 2 结点之间的路径 pass[Tree[tool][path]]--; // 该路径没被复用过,仅仅记录一次: if(pass[Tree[tool][path]]==0) { Tree[tool][path]=0; return; } // 该路径被复用过: else { tool = Tree[tool][path]; } } // 结点作为末尾数-- endd[tool]--; return; } } int word_pre(string word) { int tool=1; // 遍历工具 - 从第 1 个结点开始 int path=0; // 路径记录 // 遍历单词 从第二个结点开始记录 for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母 { path = c - 'a'; // 第 1 & 2 结点之间的路径 // 没有该结点: if(Tree[tool][path]==0) { return 0; } // 有对应结点: else { // 遍历工具访问下一结点 tool = Tree[tool][path]; } } // 返回结点通过数: return pass[tool]; } void clear() { memset(&Tree[0][0] , 0 , sizeof(int)*26*(cnt+1)); memset(&pass[0] , 0 , sizeof(int)*(cnt+1)); memset(&endd[0] , 0 , sizeof(int)*(cnt+1)); cnt=1; } int main() { cnt=1; int n; cin >> n; while(n--) { int x; string word; cin >> x >> word; if(x==1) { word_insert(word); } else if(x==2) { word_delete(word); } else if(x==3) { cout << (word_duplicate(word)>0 ? "YES" : "NO") << endl; } else { cout << word_pre(word) << endl; } } clear(); return 0; }
package class044; // 用固定数组实现前缀树,空间使用是静态的。推荐! // 测试链接 : https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的code,提交时请把类名改成"Main",可以直接通过 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.util.Arrays; public class Code02_TrieTree { // 如果将来增加了数据量,就改大这个值 public static int MAXN = 150001; public static int[][] tree = new int[MAXN][26]; public static int[] end = new int[MAXN]; public static int[] pass = new int[MAXN]; public static int cnt; public static void build() { cnt = 1; } public static void insert(String word) { int cur = 1; pass[cur]++; for (int i = 0, path; i < word.length(); i++) { path = word.charAt(i) - 'a'; if (tree[cur][path] == 0) { tree[cur][path] = ++cnt; } cur = tree[cur][path]; pass[cur]++; } end[cur]++; } public static int search(String word) { int cur = 1; for (int i = 0, path; i < word.length(); i++) { path = word.charAt(i) - 'a'; if (tree[cur][path] == 0) { return 0; } cur = tree[cur][path]; } return end[cur]; } public static int prefixNumber(String pre) { int cur = 1; for (int i = 0, path; i < pre.length(); i++) { path = pre.charAt(i) - 'a'; if (tree[cur][path] == 0) { return 0; } cur = tree[cur][path]; } return pass[cur]; } public static void delete(String word) { if (search(word) > 0) { int cur = 1; for (int i = 0, path; i < word.length(); i++) { path = word.charAt(i) - 'a'; if (--pass[tree[cur][path]] == 0) { tree[cur][path] = 0; return; } cur = tree[cur][path]; } end[cur]--; } } public static void clear() { for (int i = 1; i <= cnt; i++) { Arrays.fill(tree[i], 0); end[i] = 0; pass[i] = 0; } } public static int m, op; public static String[] splits; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); String line = null; while ((line = in.readLine()) != null) { build(); m = Integer.valueOf(line); for (int i = 1; i <= m; i++) { splits = in.readLine().split(" "); op = Integer.valueOf(splits[0]); if (op == 1) { insert(splits[1]); } else if (op == 2) { delete(splits[1]); } else if (op == 3) { out.println(search(splits[1]) > 0 ? "YES" : "NO"); } else if (op == 4) { out.println(prefixNumber(splits[1])); } } clear(); } out.flush(); in.close(); out.close(); } }
// 已经AC的代码 #include<iostream> #include<string> using namespace std; void insert(string word); void delete_(string word); // delete 是关键字,这里改为 delete_ bool search(string word); int prefixNumber(string pre); class TrieNode { // 在后续函数中全部改为指针形式 public: int path = 0; int end = 0; TrieNode *map[26] = {NULL}; // 注意这里要加 * 号 ,注意一定要把指向对象的数组指向NULL }; TrieNode *root = new TrieNode(); // 注意一定要写 new TrieNode() void insert(string word) { if (word.empty()) { return; } TrieNode *node = root; node->path++; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (node->map[index] == NULL) { node->map[index] = new TrieNode(); } node = node->map[index]; node->path++; } node->end++; } void delete_(string word) { if (search(word)) { TrieNode *node = root; node->path++; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (node->map[index]->path-- == 1) { node->map[index] = NULL; return; } node = node->map[index]; } node->end--; } } bool search(string word) { if (word.empty()) { return false; } TrieNode *node = root; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (node->map[index] == NULL) { return false; } node = node->map[index]; } return node->end != 0; } int prefixNumber(string pre) { if (pre.empty()) { return 0; } TrieNode *node = root; int index = 0; for (int i = 0; i < pre.size(); i++) { index = pre[i] - 'a'; if (node->map[index] == NULL) { return 0; } node = node->map[index]; } return node->path; } int main() { int m; cin >> m; while (m--) { int op; cin >> op; if (op == 1) { string word; cin >> word; insert(word); } if (op == 2) { string word; cin >> word; delete_(word); } if (op == 3) { string word; cin >> word; bool res = search(word); cout << (res ? "YES" : "NO") << endl; } if (op == 4) { string word; cin >> word; int res = prefixNumber(word); cout << res << endl; } } return 0; }
#include<iostream> #include<string> #include<cstring> using namespace std; const int N = 26; class Node{ public: Node(); ~Node(); /* void insert(string word); void deleteStr(string word); bool search(string word); int prefixNumber(string pre); */ int pass; int end; Node *next[N]; }; Node::Node() { this->pass = 0; this->end = 0; memset(this->next,NULL,sizeof(next)); } Node::~Node() { for(int i = 0; i < N; i++) { if(this->next[i] != NULL) { delete this->next[i]; this->next[i] = NULL; } } } bool search(Node * root ,string word); //op = 1 void insert(Node * root , string word) { if(word.size() == 0) return; Node* node = root; node->pass++; int index = 0; for(int i = 0; i < word.size() ; i++) { index = word[i] - 'a'; if(node->next[index] == NULL) node->next[index] = new Node; node = node->next[index]; node->pass++; } node->end++; } //op = 2 void deleteStr(Node *root ,string word) { if(!search(root,word)) return; Node *node = root; int index = 0; node->pass--; for(int i = 0; i < word.size(); i++) { index = word[i] - 'a'; node->next[index]->pass--; if(node->next[index]->pass == 0) { delete node->next[index]; node->next[index] = NULL; return; } node = node->next[index]; } } //op = 3 bool search(Node * root ,string word) { if(word.size() == 0) return false; Node *node = root; int index = 0; for(int i = 0 ; i < word.size() ; i++) { index = word[i] - 'a'; if(node->next[index] == NULL) return false; node = node->next[index]; } return true; } //op = 4 int prefixNumber(Node * root ,string pre) { if(pre.size() == 0) return root->pass; Node *node = root; int index = 0; for(int i = 0; i < pre.size(); i++) { index = pre[i] - 'a'; node = node->next[index]; } return node->pass; } int main(){ Node *root = new Node; int m ; cin >> m; for(int i = 0; i < m; i++) { int op; string str; cin >> op; cin >> str; if(op == 1) insert(root,str); else if(op == 2) deleteStr(root,str); else if(op == 3) cout << (search(root,str) ? "YES" : "NO") << endl; else if(op == 4) cout << prefixNumber(root,str) << endl; } delete root; return 0; }有哪位大神能帮我看看,为什么我这个会发生段错误,谢谢
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { // 根节点 private static TireNode root = new TireNode(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int opNum = in.nextInt(); while (opNum-- > 0) { int op = in.nextInt(); String str = in.next(); switch (op) { case 1: addNode(str); break; case 2: delNode(str); break; case 3: System.out.println(ifExitNode(str) ? "YES" : "NO"); break; case 4: System.out.println(getSubNodeCnt(str)); } } } private static int getSubNodeCnt(String prefix) { TireNode node = root; for (char c : prefix.toCharArray()) { if (!node.subNode.containsKey(c)) { return 0; } node = node.subNode.get(c); } return node.cnt; } private static boolean ifExitNode(String str) { TireNode node = root; for (char c : str.toCharArray()) { if (!node.subNode.containsKey(c)) { return false; } node = node.subNode.get(c); } return node.end != 0; } // 删除node的时候 每次只能删一个 即使重复了好几个 每次也只能删一个 private static void delNode(String str) { TireNode node = root; for (char c : str.toCharArray()) { node = node.subNode.get(c); node.cnt--; } node.end--; if (node.cnt == 0) { node.subNode = new HashMap<>(); } } // 可以重复添加的node private static void addNode(String str) { TireNode node = root; for (char c : str.toCharArray()) { if (!node.subNode.containsKey(c)) { node.subNode.put(c, new TireNode()); } node = node.subNode.get(c); node.cnt++; } node.end++; } static class TireNode { // 其实可以换成数组 public Map<Character, TireNode> subNode = new HashMap<>(); // 多少个单词路过这个节点 public int cnt = 0; // 这个节点是多少个单词的结尾 // 这点可以重复添加,这是最骚的 public int end = 0; } }