実質2行で定義するTrie木（とその改造例） #競技プログラミング – Qiita

n = int(input())
s = input().split()

tree = {}
ans = 0
for t in s:
    current = tree
    for c in t:
        if c in current:
            ans += current[c][0]
            current[c][0] += 1
        else:
            current[c] = [1, {}]
        current = current[c][1]
print(ans)

struct Node {
    int cnt = 0;
    mapchar, Node*> to;
};

#include 
#include 
#include 
using namespace std;

struct Node {
    int cnt = 0;
    mapchar, Node*> to;
};

int main() {
    int n;
    cin >> n;
    Node root;
    long long ans = 0;

    for (int i = 0; i  n; i++) {
        string s;
        cin >> s;
        Node* now = &root;
        for (char c : s) {
            if (now->to.count(c)) {
                ans += now->to[c]->cnt;
            } else {
                now->to[c] = new Node;
            }
            now->to[c]->cnt++;
            now = now->to[c];
        }
    }

    cout  ans  endl;
    return 0;
}

#include 
#include 
#include 

using namespace std;

struct Node {
    int cnt = 0;              // このノードに到達した文字列の本数
    mapchar, Node*> to;      // 次の文字へのポインタ
};

int main() {
    int n;
    cin >> n;
    Node root;

    // 入力される n 個の文字列を Trie に挿入
    for (int i = 0; i  n; ++i) {
        string s;
        cin >> s;
        Node* now = &root;
        now->cnt++;           // 空文字列もカウント
        for (char c : s) {
            if (!now->to.count(c)) {
                now->to[c] = new Node();
            }
            now = now->to[c];
            now->cnt++;
        }
    }

    string path;

    // DFSでTrieを探索
    auto dfs = [&](auto& dfs, Node* now) -> void {
        cout  now->cnt  " "  path  endl;
        for (auto& [key, next] : now->to) {
            path.push_back(key);
            dfs(dfs, next);
            path.pop_back();
        }
    };

    dfs(dfs, &root);
}

5
fire
firearm
firework
fireman
algo

5 
1 a
1 al
1 alg
1 algo
4 f
4 fi
4 fir
4 fire
1 firea
1 firear
1 firearm
1 firem
1 firema
1 fireman
1 firew
1 firewo
1 firewor
1 firework

#include 
using namespace std;

// Trie のノード構造体
struct Node {
    int cnt = 0;                   // このノードまで到達した文字列の個数
    mapchar, Node*> to;           // 次の文字への枝（子ノードへのポインタ）
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 入力される n 個の文字列を格納
    vectorstring> ss(n);
    for(int i = 0; i  n; i++){
        cin >> ss[i];
    }

    // Trie の根ノードを動的に確保
    Node* root = new Node();

    // 1) Trie の構築フェーズ
    for(const string& s : ss){
        Node* now = root;
        now->cnt++;               // 空文字もカウント（各文字列の先頭に到達したので +1）
        for(char c : s){
            // 枝がなければ新しくノードを作成
            if(now->to.find(c) == now->to.end()){
                now->to[c] = new Node();
            }
            // 子ノードへ移動してカウントをインクリメント
            now = now->to[c];
            now->cnt++;
        }
    }

    // 2) 各文字列について「他の文字列と共有している最大の接頭辞長」を求めるフェーズ
    for(const string& s : ss){
        Node* now = root;
        int idx = 0;
        int m = s.size();

        // 文字を一文字ずつたどり、到達ノードの cnt が 2 以上なら idx++ して深さを伸ばす
        while(idx  m){
            char c = s[idx];
            Node* next = now->to[c];
            if(next->cnt  1){
                // この枝を通る文字列が自分しかいない → 共有はここまで
                break;
            }
            now = next;
            idx++;
        }

        // idx が他の文字列と共有している最大の長さ
        cout  idx  "\n";
    }

    return 0;
}