#include <iostream>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

struct TNode {
    TNode(char letter = '\0')
        : Letter(letter)
    {
    }
    void AddWord(const std::string& word, size_t n) {
        if (n == word.size()) {
            return;
        }
        for (size_t i = 0; i < Childs.size(); ++i) {
            if (Childs[i].Letter == word[n]) {
                Childs[i].AddWord(word, n + 1);
                return;
            }
        }
        Childs.push_back(TNode(word[n]));
        Childs[Childs.size() - 1].AddWord(word, n + 1);
    }
    void CalcStats(size_t& singleChildNodesCount, size_t& totalNodesCount) {
        if (Letter) {
            ++totalNodesCount;
            if (Childs.size() == 1) {
                ++singleChildNodesCount;
            }
        }
        for (size_t i = 0; i < Childs.size(); ++i) {
            Childs[i].CalcStats(singleChildNodesCount, totalNodesCount);
        }
    }
    char Letter;
    vector<TNode> Childs;
};

class TRadixTree {
public:
    void AddWord(const std::string& word) {
        Root.AddWord(word, 0);
    }
    void CalcStats(size_t& singleChildNodesCount, size_t& totalNodesCount) {
        Root.CalcStats(singleChildNodesCount, totalNodesCount);
    }
private:
    TNode Root;
};

int main()
{
    TRadixTree tree;
    std::ifstream file("/home/fippo/words.txt");

    std::string word;
    while (std::getline(file, word)) {
        tree.AddWord(word);
    }

    size_t singleChildNodesCount = 0;
    size_t totalNodesCount = 0;
    tree.CalcStats(singleChildNodesCount, totalNodesCount);

    cout << "Total:         " << totalNodesCount << "\n";
    cout << "Single childs: " << singleChildNodesCount << "\n";
    cout << "Single childs: " << 100.0 * singleChildNodesCount / totalNodesCount << "\n";

    return 0;
}

/*
Total:         451238
Single childs: 304670
Single childs: 67.5187
*/