灵异事件?

P8306 【模板】字典树

Geirangerfjard @ 2023-11-24 19:30:04

代码样例都过不去,提交 AC ?

#include <bits/stdc++.h>

#define int long long
#define LL long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mem(a, v) memset(a, v, sizeof a)
#define re read()

const int N = 3e6 + 2, M = 65;

using namespace std;

inline LL read()
{
    int num = 0;char c;bool flag = false;
    while((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if(c == '-') flag = true;else num = c - '0';
    while(isdigit(c = getchar())) num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;   
} 

/*
Contest : 
Problem : 
Day : 23/11/24
Start coding at 
End coding at 
Finish debuging at 
*/

const int mod = 998244353;

int _;

int n, q, idx;

int t[N][M], p[N], cnt[N];

char s[N];

int getnum(char ch)
{
    if (ch >= 'A' && ch <= 'Z') return ch - 'A';
    else if (ch >= 'a' && ch <= 'z') return ch - 'a' + 26;
    else return ch - '0' + 52;
} 

void insert(char *str)
{
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i ++ )
    {
        int c = getnum(str[i]);
        if (!t[p][c]) t[p][c] = ++ idx;
        p = t[p][c];
        ++ cnt[p];
    }
}

int find(char *str)
{
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i ++ )
    {
        int c = getnum(str[i]);
        if (!t[p][c]) return 0;
        p = t[p][c];
    }
    return cnt[p];
}

void solve()

{
    for (int i = 0; i <= idx; i ++ )
        for (int j = 0; j <= 122; j ++ )
            t[i][j] = 0;

    for (int i = 0; i <= idx; i ++ ) cnt[i] = 0;
    idx = 0;
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i ++ ) scanf("%s", s), insert(s);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%s", s);
        printf("%lld\n", find(s));
    } 
}

signed main()

{
    //IOS;

    _ = 1;
    //_ = re;
    //cin >> _;
    scanf("%lld", &_);

    while (_ -- ) solve();

    return 0;
}

/*
Coding by Geirangerfjard.
Miss her.
*/ 

by Disjoint_cat @ 2023-11-24 19:53:49

经典 UB 现象。

自己好好看看写的什么。

const int N = 3e6 + 2, M = 65;
...
int t[N][M], p[N], cnt[N];
...
for (int i = 0; i <= idx; i ++ )
    for (int j = 0; j <= 122; j ++ )
        t[i][j] = 0;

你确定这里 j 是循环到 122


by wangqing111 @ 2023-11-24 20:06:50

666


|