//50pts代码求调
#include <iostream>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd;

    TrieNode() {
        isEnd = false;
    }
};

class Trie {
private:
    TrieNode* root;
    int count;  // 统计不同字符串的数量

public:
    Trie() {
        root = new TrieNode();
        count = 0;
    }

    void insert(string word) {
        TrieNode* current = root;
        bool isNew = false;
        for (char ch : word) {
            if (current->children.find(ch) == current->children.end()) {
                current->children[ch] = new TrieNode();
                isNew = true;  // 遇到新的字符
            }
            current = current->children[ch];
        }
        if (isNew) {
            count++;  // 如果遇到新的字符串,则数量加一
        }
        current->isEnd = true;
    }

    int getCount() {
        return count;
    }
};

int main() {
    int n;
    cin >> n; // 输入整数n
    Trie trie;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word; // 输入每个字符串
        trie.insert(word);
    }
    int result = trie.getCount(); // 获取不同字符串的数量
    cout << result << endl;  // 输出结果
    return 0;
}

1 comments

  • @ 2024-3-16 20:15:52
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int n, p = 1, trie[10000005][26], size[10000005];
    char s[4000005];
    
    void insert(int u, const char* s) {
    if (!strlen(s)) {
    size[u] = 1;
    return;
    }
    if (!trie[u][s[0] - 'a']) trie[u][s[0] - 'a'] = ++p;
    insert(trie[u][s[0] - 'a'], s + 1);
    }
    
    void calcsize(int u) {
    for (int i = 0; i < 26; i++) {
    if (trie[u][i]) {
    calcsize(trie[u][i]);
    size[u] += size[trie[u][i]];
    }
    }
    }
    
    int main() {
    std::ios::sync_with_stdio(false);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    insert(1, s);
    }
    calcsize(1);
    printf("%d\n", size[1]);
    return 0;
    }
    
    • 1

    Information

    ID
    180
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    3
    Tags
    # Submissions
    1857
    Accepted
    260
    Uploaded By