17 条题解

  • 6
    @ 2022-3-3 10:47:28

    在添加字符串结尾的时候判断一下,之前是否已经是结尾,如果不是ans++,如果是就不执行++操作。最后主函数直接输出ans即可。

    #include<iostream>
    using namespace std;
    
    typedef long long ll;
    
    const int N = 1e7;
    
    int n,m,ans = 0;
    int trie[N][26],tot = 1;
    bool End[N];
    
    void insert(string str)
    {
        int len = str.length(),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];
        }
        if(!End[p])
        {
            End[p] = true;
            ans ++;
        }
    }
    
    string str;
    
    int main()
    {
        cin >> n;
        while(n --)
        {
            cin >> str;
            insert(str);
        }
        cout << ans << endl;
    }
    

    信息

    ID
    180
    时间
    300~1000ms
    内存
    1024MiB
    难度
    3
    标签
    递交数
    2626
    已通过
    353
    上传者