关于字典树的题目，奇怪的是：

额外减小

最后一个点AC了 。
其他点都是RE。
是不是说明我的整体思路没毛病？

评测记录
https://www.luogu.com.cn/record/126745207
题目链接
https://www.luogu.com.cn/problem/P8306

rt.

我真的不理解，最后一个点AC是不是表示整体的逻辑没问题？

但找不到RE的原因。

求调，感激不尽

马蜂有点怪。希望您能原谅。

1. #include <iostream>
   
2. #include <cstring>
   
3. #include <cstdlib>
   
4. using namespace std;
   
5. 
   
6. struct Node {
   
7.     char data;
   
8.     Node* next[60];
   
9.     int down_cnt;
   
10. };
    
11. 
    
12. typedef Node* Trie;
    
13. 
    
14. int trans(char ch) {
    
15.     if (ch >= 'A' && ch <= 'Z')
    
16.         return ch - 'A';
    
17.     return ch - 'a' + 26;
    
18. }
    
19. 
    
20. Trie init_Trie() {
    
21.     Trie trie = new Node;
    
22.     trie->data = '\0';
    
23.     trie->down_cnt = 0;
    
24.     memset(trie->next, 0, sizeof(trie->next));
    
25.     return trie;
    
26. }
    
27. 
    
28. void add(const char* str, Trie trie) {
    
29.     Trie ptr = trie;
    
30.     int len = strlen(str);
    
31.     for (int i = 0; i < len; i++) {
    
32.         if (ptr->next[trans(str[i])] == nullptr) {
    
33.             ptr->next[trans(str[i])] = init_Trie();
    
34.             ptr->next[trans(str[i])]->data = trans(str[i]);
    
35.         }
    
36.         ptr->down_cnt++;
    
37.         ptr = ptr->next[trans(str[i])];
    
38.     }
    
39. }
    
40. 
    
41. void dfs(const char* str, int p, int len, Trie &trie) {
    
42.     if (p == len - 1) {
    
43.         cout << trie->down_cnt << endl;
    
44.         return;
    
45.     }
    
46.     if(trie->next[trans(str[p])]==nullptr)
    
47.     {
    
48.         cout<<0<<endl;
    
49.         return ;
    
50.     }
    
51.     dfs(str, p + 1, len, trie->next[trans(str[p])]);
    
52. }
    
53. 
    
54. void free_Trie(Trie trie) {
    
55.     if (trie == nullptr) {
    
56.         return;
    
57.     }
    
58.     for (int i = 0; i < 60; i++) {
    
59.         free_Trie(trie->next[i]);
    
60.     }
    
61.     delete trie;
    
62. }
    
63. 
    
64. int main() {
    
65.     int t, n, q;
    
66.     string str;
    
67.     cin >> t;
    
68.     while (t--) {
    
69.         Trie trie = init_Trie();
    
70.         cin >> n >> q;
    
71.         for (int i = 0; i < n; i++) {
    
72.             cin >> str;
    
73.             add(str.c_str(), trie);
    
74.         }
    
75.         for (int i = 0; i < q; i++) {
    
76.             cin >> str;
    
77.             dfs(str.c_str(), 0, strlen(str.c_str()), trie);
    
78.         }
    
79.         free_Trie(trie);
    
80.     }
    
81. 
    
82.     return 0;
    
83. }

复制代码

陶远航

在这个问题中，RE错误通常会发生在内存访问超出范围时。在查看代码后，我发现可能存在以下问题：

1. 在 for 循环中，当对指针进行解引用并访问下一个字符的 next 指针时，可能会访问到空指针。在调用 add 函数时，应该先判断 ptr->next[trans(str[ i])] 是否为 nullptr。

2. 在递归 dfs 函数时，如果在字典树中找不到对应的字符节点，也会访问到空指针。在递归之前，应该首先判断 trie->next[trans(str[p])] 是否为 nullptr。

因此，可以尝试使用以下代码实现修复：

1. void add(const char* str, Trie trie) {
   
2.     Trie ptr = trie;
   
3.     int len = strlen(str);
   
4.     for (int i = 0; i < len; i++) {
   
5.         if (ptr->next[trans(str[ i])] == nullptr) {
   
6.             ptr->next[trans(str[ i])] = init_Trie();
   
7.             ptr->next[trans(str[ i])]->data = trans(str[ i]);
   
8.         }
   
9.         ptr->down_cnt++;
   
10.         ptr = ptr->next[trans(str[ i])];
    
11.     }
    
12. }
    
13. 
    
14. void dfs(const char* str, int p, int len, Trie &trie) {
    
15.     if (trie == nullptr) {
    
16.         cout << 0 << endl;
    
17.         return;
    
18.     }
    
19.     if (p == len - 1) {
    
20.         cout << trie->down_cnt << endl;
    
21.         return;
    
22.     }
    
23.     dfs(str, p + 1, len, trie->next[trans(str[p])]);
    
24. }
    
25. 
    
26. int main() {
    
27.     int t, n, q;
    
28.     string str;
    
29.     cin >> t;
    
30.     while (t--) {
    
31.         Trie trie = init_Trie();
    
32.         cin >> n >> q;
    
33.         for (int i = 0; i < n; i++) {
    
34.             cin >> str;
    
35.             add(str.c_str(), trie);
    
36.         }
    
37.         for (int i = 0; i < q; i++) {
    
38.             cin >> str;
    
39.             dfs(str.c_str(), 0, strlen(str.c_str()), trie);
    
40.         }
    
41.         free_Trie(trie);
    
42.     }
    
43.     return 0;
    
44. }
    

复制代码

同时，可以推荐一些调试技巧来帮助你寻找RE的原因：

1. 在本地使用调试器，例如GDB或LLDB，可以在程序崩溃时捕获Core Dump并分析其堆栈跟踪。这可以帮助你更好地了解程序何时崩溃，以及在哪个函数中发生了错误。

2. 手动添加调试输出语句，例如打印变量值、循环计数器等，以便更好地了解程序的执行流程和问题出现的位置。

3. 尝试使用在线调试工具，例如IDEOne或CodeSandbox，可以模拟在线评测平台的环境，并提供更多的调试选项和错误消息。
如果问题已经解决，请设置最佳答案

额外减小

isdkz 发表于 2023-9-30 20:55
这道题目的问题在于在添加字符串时没有对最后一个节点的 down_cnt 进行更新。在 dfs 的过程中，如果遇到了 ...

好好好

额外减小

@元豪 @zhangjinxuan @Mike_python小 @Ewan-Ahiouy @sfqxx

Ewan-Ahiouy

没有学过

陶远航

isdkz 发表于 2023-9-30 20:55
这道题目的问题在于在添加字符串时没有对最后一个节点的 down_cnt 进行更新。在 dfs 的过程中，如果遇到了 ...

代码？

isdkz

陶远航 发表于 2023-9-30 22:05
代码？

可能是超过token限制了