大家帮忙看看为什么不用memset了还是答案错误

P8306 【模板】字典树

fufuQAQ @ 2022-10-25 10:15:13

//这题只要判断出这个字符串是否存在即可 
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 3*1e6+10;

int cnt[M];
int trie[M][60], tot = 1;//初始化 
char str[M];

void insert(char* str)//插入一个字符串 
{
    int len = strlen(str), p = 1;
    for (int k = 0; k < len; k++){
        int ch = str[k] - 'a';
        if (trie[p][ch] == 0)
            trie[p][ch] = ++tot;//这个地方放得是位置 
        p = trie[p][ch];
        cnt[p]++; 
    }
}

int search(char* str)//检索字符串是否存在 
{
    int len = strlen(str), p = 1;
    for (int k = 0; k < len; k++)
    {
        p = trie[p][str[k] - 'a'];
        if (p == 0) 
            return false;
    }
    return cnt[p];
}

int main(void)
{
    int t;
    cin>>t;
    while(t--)
    {
    for (int i = 0; i <= tot; i++)
      for (int j = 0; j <= 'z'; j++)
        trie[i][j] = 0;
    for (int i = 0; i <= tot; i++)
        cnt[i] = 0;
        tot=1;
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            cin >> str;
            insert(str);
        }
        for (int i = 0; i < m; i++)
        {
            cin >> str;
            cout << search(str) << endl;
        }
    }
    return 0;
}

前四个点是错的

by HHHashtable @ 2022-10-28 16:52:21

@fufuQAQ 输入的字符包含字母大小写及数字

int ch = str[k] - 'a';

当字母不为小写时直接减会成负数

by fufuQAQ @ 2022-10-29 19:06:55

@天汉CbIH 改成这样也还是错啊，帮帮忙改改呗

int ch = str[k] - '0';

by HHHashtable @ 2022-10-29 20:39:34

@fufuQAQ 你可以把它改成一个函数,像这样

int Atoi(char x)//x为str[k]
{
    if(x>='0'&&x<='9')
    {
        return x-'0';   
    }
    if(x>='a'&&x<='z')
    {
        return x-'a'+10;
    }
    if(x>='A'&&x<='Z')
    {
        return x-'A'+36;
    }
}

另外,大小写字母加数字总共62种字符,trie树要开62维,不然可能会RE

还有在清空trie树时直接

for (int i = 0; i <= tot; i++)
      for (int j = 0; j <= 61; j++)
        trie[i][j] = 0;

就可以了

|