Any two strings s₁, s₂ have a common prefix cp, which is the string of characters that s₁ and s₂ have in common up from the start. If s₁, s₂ have no such common characters, cp is the empty string. Let s̅₁, s̅₂ be the remainders or suffixes of s₁ and s₂ if cp is removed from them. Then, the common prefix notation (CPN) of s₁, s₂ – in short, cpn(s₁,s₂) – shall be:

cpn(s1,s2) := cp{s̅1,s̅2}

Given the definition above, for any given CPN of a set of strings s₁, s₂, …, s_n, the CPN of the set extended by an additional string s_n+1 is defined as follows:

Case 1: If the suffix of s_n+1 with cp removed, s̅_n+1, has no nonempty common prefix with any of the suffixes s̅₁, s̅₂, …, s̅_n:

cpn(s1,s2,…,sn+1) := cp{s̅1,s̅2,…,s̅n+1}

Case 2: Otherwise, since the first characters of s̅₁, s̅₂, …, s̅_n are distinct, there can only be one element s̅_m that has a nonempty common prefix with s̅_n+1. Given s̅_m to be that element:

cpn(s1,s2,…,sn+1) := cp{s̅1,s̅2,…,cpn(s̅m,s̅n+1),…,s̅n}

Examples:

cpn("a", "b") = "{a,b}"
cpn("aa", "ab") = "a{a,b}"
cpn("aa", "ab", "abc", "abd") = "a{a,b{c,d}}"
cpn("a", "ab", "abc") = "{a{b{c}}}"

Note: For the sake of reasoning, strings containing the CPN’s reserved characters {, } and , shall be considered invalid input. In a practical implementation, a syntax for „escaping“ these reserved characters should be available.

Given a set of strings, one per line, on standard input, the following Python program prints the CPN of these strings on standard output: http://tk-sls.de/ref/trie1.py

Try the examples:

./trie1.py << EOF
a
b
EOF

./trie1.py << EOF
aa
ab
EOF

./trie1.py << EOF
aa
ab
abc
abd
EOF

The following example renders the wrong output, because a trie does not actually store the common prefix (this is what a suffix tree would accomplish), it just stores different prefix paths, and a, ab and abc have no different prefix paths, it’s just a degenerate tree a → b → c:

./trie1.py << EOF
a
ab
abc
EOF

So my guess is, i must implement one of these fancy suffix tree algorithms to get it done right. (see the update instead) 🙂

In the meantime, try this:

find /etc -type d | ./trie1.py

🙂