#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    bool end=0;
    int next[30];
};
vector<node>trie;
node emp;
bool find(string str){
    int nd=1;
    bool found=1;
    for(int i=0;i<str.size();i++){
        if(trie[nd].next[str[i]-'a']==-1){
            found=0;
            trie.push_back(emp);
            trie[nd].next[str[i]-'a']=trie.size()-1;
        }
        nd=trie[nd].next[str[i]-'a'];
    }
    if(!trie[nd].end) found=0,trie[nd].end=1;
    return found;
}
signed main(){
    emp.end=0;
    for(int i=0;i<30;i++) emp.next[i]=-1;
    trie.push_back(emp);
    trie.push_back(emp);
    int cnt=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string k;
        cin>>k;
        if(!find(k)) cnt++;
    }
    cout<<cnt;
    return 0;
}

4 条评论

  • @ 2021-10-1 7:19:38

    ok,谢谢大佬!

    • @ 2021-9-25 17:10:27

      vector 的 push_back 常数过大,预先 resize 就可以了吧。

      • @ 2021-9-25 17:10:02

        提问的时候麻烦说清楚,看了眼提交记录才发现你是 TLE。😑

        • @ 2021-9-25 14:26:33

          find 函数的倒数第二行 trie[nd].end=false 的时候应该让 found=1 吧。

          • @ 2021-9-25 15:16:07

            不是啊,如果end=0就说明没有出现过,只出现过含有他的串啊

        • 1

        信息

        ID
        180
        时间
        1000ms
        内存
        256MiB
        难度
        3
        标签
        递交数
        2650
        已通过
        355
        上传者