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

额外减小

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

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

rt.

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

但找不到RE的原因。

求调，感激不尽

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

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

struct Node {
    char data;
    Node* next[60];
    int down_cnt;
};

typedef Node* Trie;

int trans(char ch) {
    if (ch >= 'A' && ch <= 'Z')
        return ch - 'A';
    return ch - 'a' + 26;
}

Trie init_Trie() {
    Trie trie = new Node;
    trie->data = '\0';
    trie->down_cnt = 0;
    memset(trie->next, 0, sizeof(trie->next));
    return trie;
}

void add(const char* str, Trie trie) {
    Trie ptr = trie;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (ptr->next[trans(str[i])] == nullptr) {
            ptr->next[trans(str[i])] = init_Trie();
            ptr->next[trans(str[i])]->data = trans(str[i]);
        }
        ptr->down_cnt++;
        ptr = ptr->next[trans(str[i])];
    }
}

void dfs(const char* str, int p, int len, Trie &trie) {
    if (p == len - 1) {
        cout << trie->down_cnt << endl;
        return;
    }
    if(trie->next[trans(str[p])]==nullptr)
    {
        cout<<0<<endl;
        return ;
    }
    dfs(str, p + 1, len, trie->next[trans(str[p])]);
}

void free_Trie(Trie trie) {
    if (trie == nullptr) {
        return;
    }
    for (int i = 0; i < 60; i++) {
        free_Trie(trie->next[i]);
    }
    delete trie;
}

int main() {
    int t, n, q;
    string str;
    cin >> t;
    while (t--) {
        Trie trie = init_Trie();
        cin >> n >> q;
        for (int i = 0; i < n; i++) {
            cin >> str;
            add(str.c_str(), trie);
        }
        for (int i = 0; i < q; i++) {
            cin >> str;
            dfs(str.c_str(), 0, strlen(str.c_str()), trie);
        }
        free_Trie(trie);
    }

    return 0;
}

陶远航

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

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

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

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

void add(const char* str, Trie trie) {
    Trie ptr = trie;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (ptr->next[trans(str[ i])] == nullptr) {
            ptr->next[trans(str[ i])] = init_Trie();
            ptr->next[trans(str[ i])]->data = trans(str[ i]);
        }
        ptr->down_cnt++;
        ptr = ptr->next[trans(str[ i])];
    }
}

void dfs(const char* str, int p, int len, Trie &trie) {
    if (trie == nullptr) {
        cout << 0 << endl;
        return;
    }
    if (p == len - 1) {
        cout << trie->down_cnt << endl;
        return;
    }
    dfs(str, p + 1, len, trie->next[trans(str[p])]);
}

int main() {
    int t, n, q;
    string str;
    cin >> t;
    while (t--) {
        Trie trie = init_Trie();
        cin >> n >> q;
        for (int i = 0; i < n; i++) {
            cin >> str;
            add(str.c_str(), trie);
        }
        for (int i = 0; i < q; i++) {
            cin >> str;
            dfs(str.c_str(), 0, strlen(str.c_str()), trie);
        }
        free_Trie(trie);
    }
    return 0;
}

同时，可以推荐一些调试技巧来帮助你寻找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限制了