求助!

P8306 【模板】字典树

CaiZi @ 2023-12-23 21:59:21

以下是 1 份正常代码,但是加入我把第 3 行的 128 改为 80,清空数组同样处理,可以过样例,也可以 AC 本题,但小写字母应该是无法处理的,且速度比正确写法快半秒,求合理解释。改成再小的数就不行了。

#include<bits/stdc++.h>
using namespace std;
int w,n,q,u,m,x[3145141][128],y[3145141],cnt;
string s;
char t;
bool flag;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>w;
    while(w--){
        cin>>n>>q;
        for(int i=0;i<=cnt;i++){
            for(int j=0;j<=127;j++){
                x[i][j]=0;
            }
            y[i]=0;
        }
        cnt=0;
        for(int i=1;i<=n;i++){
            cin>>s;
            m=s.length();
            u=0;
            for(int j=0;j<m;j++){
                t=s[j];
                if(!x[u][t]){
                    x[u][t]=++cnt;
                }
                u=x[u][t];
                y[u]++;
            }
        }
        for(int i=1;i<=q;i++){
            cin>>s;
            m=s.length();
            u=0;
            flag=true;
            for(int j=0;j<m;j++){
                t=s[j];
                if(!x[u][t]){
                    flag=false;
                    break;
                }
                u=x[u][t];
            }
            cout<<(flag?y[u]:0)<<'\n';
        }
    }
    return 0;
}

|