trie求条
查看原帖
trie求条
774876
HashHacker_Peas楼主2025/7/2 18:25

rt,感觉思路没什么问题,为什么会WA,代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int t,n,tr[maxn][30],tot,ed[maxn];
string s[maxn];
void init(){
    tot=0;
    memset(tr,0,sizeof(tr));
    memset(ed,0,sizeof(ed));
}
void insert(string s){
    int p=1;
    for(int i=0;i<s.length();i++){
        int x=s[i]-'0';
        if(!tr[p][x])
            tr[p][x]=++tot;
        p=tr[p][x];
    }
    ed[p]++;
}
bool check(string s){
    bool flag=false;
    int p=1;
    for(int i=0;i<s.length();i++){
        int x=s[i]-'0';
        p=tr[p][x];
        if(ed[p]>=1&&i!=s.length()-1)
            return true;
    }
    for(int i=0;i<=26;i++)
        flag|=tr[p][i];
    return flag;
}
int main(){
    cin>>t;
    while(t--){
        init();
        cin>>n;
        bool flag=false;
        for(int i=1;i<=n;i++)
            cin>>s[i],insert(s[i]);
        for(int i=1;i<=n;i++)
            flag|=check(s[i]);
        cout<<(flag?"NO\n":"YES\n");
    }
    return 0;
}
2025/7/2 18:25
加载中...