A trie implementation to this question https://uva.onlinejudge.org/external/125/p12526.pdf

trie-implementation.cpp

#include <bits/stdc++.h>
#define ALPHABET_SIZE 27
using namespace std;
class TrieNode
{
	public: TrieNode* children[ALPHABET_SIZE];

	public: int qntChild;
	public: bool endWord;

	public: TrieNode(bool endWord)
	{
		this->endWord = endWord;
		this->qntChild = 0;

		for(int i = 0;i < ALPHABET_SIZE;i++)
			children[i] = NULL;
	}
};

TrieNode *root = new TrieNode(true);

void insert(string &str)
{
	TrieNode *node = root;
	for(int i = 0;i < str.size();i++)
	{
		int c = str[i] - 'a';
		if(node->children[c] == NULL)
		{
			node->children[c] = new TrieNode(false);
			node->qntChild++;
		}
		node = node->children[c];
	}
	node->endWord = true;
}

int search(string &str)
{
	TrieNode *node = root;
	int result = 0;
	for(int i = 0;i < str.size();i++)
	{
		int c = str[i] - 'a';
		if(node->children[c] == NULL)
			return -1;
		if(node->qntChild == 1 && node->endWord == false)
			result++;
		node = node->children[c];
	}
	return str.size() - result;
}

void deletion(TrieNode *node)
{
	for(int i = 0;i < ALPHABET_SIZE;i++)
	{
		if(node->children[i] != NULL)
		{
			deletion(node->children[i]);
			node->children[i] = NULL;
			delete node->children[i];
		}
	}
}

int main()
{
	int n;
	string str[100005];
	while(~scanf("%d", &n))
	{
		for(int i = 0;i < n;i++)
		{
			cin>>str[i];
			insert(str[i]);
		}
		int sum = 0;
		for(int i = 0;i < n;i++)
		{
			//cout<<search(str[i])<<endl;
			sum += search(str[i]);
		}
		printf("%.2lf\n", (double)sum/n);
		deletion(root);
	}
	return 0;
}