Culling strings from a list that are substrings of other list elements
All in all this looks good already.

A few tips:

continue

If you change the test in explode from if s: to 

if not s:
    continue


You can save a level of indentation for the rest of the loop

collections.defaultdict

checking whether a key is in a dict, and adding it if it isn't is why there is collections.defaultdict which can simplify explode a lot:

def explode(subject: Iterable[str]) -&gt; Exploded:
    heads_to_tails = defaultdict(list)
    for s in subject:
        if not s:
            continue
        heads_to_tails[s[0]].append(s[1:])
    return {h: prune_or_follow(t) for (h, t) in heads_to_tails.items()}


tuple unpacking

A matter of style, but in most situations where you use my_list[0] and my_list[1:], you can use tuple unpacking. You can use this in prune_or_follow

def prune_or_follow(tails: List[str]) -&gt; Union[Exploded, str]:
    start, *rest = tails
    if rest:
        return explode(tails)
    else:  
        return start


Whether this is more clear is a matter of taste.

This tuple unpacking does not work as clean in explode because it converts the string into a list of 1-character strings.

Exploded

You can use a string in typing so you can do:

Exploded = Dict[str, Union["Exploded", str]]


without the Exploded = None

cull typing

cull can accept any iterable. For the result, I don't think the order of strings is important, so there is no need to limit you to a list. The signature can then be def cull(subject: Iterable[str]) -&gt; Collection[str]:. Whether you return a list or a set is a matter of implementation. 

If the result is just used for iteration, you can even forgo the list call, and just return the implode generator, and let the caller decide whether he needs in in a list, set or whatever data structure he wants.

implode

now you use e as argument name. One-letter variable names are unclear in general, and to be avoided most of the time*. Since it is a kind of a tree, I would change this variable.

A slightly different take in implode which doesn't use string concatenation but tuple unpacking:

def implode(tree: Exploded, previous=()) -&gt; Generator[str, None, None]:
    for root, branches in tree.items():
        if isinstance(branches, str):
            yield "".join((*previous, root, *branches))
        else:
            yield from implode(branches, *previous, root)


or equivalently:

def implode(tree: Exploded, previous=()) -&gt; Generator[str, None, None]:
    for root, branches in tree.items():
        if isinstance(branches, str):
            yield "".join((*previous, root, *branches))
        else:
            yield from implode(branches, (*previous, root))


The choice between your version and this is a matter of taste, but I wanted to present the different possibilities.

Another variation, is using try-except ArgumentError instead of the isinstance:

def implode_except(tree: Exploded, previous=()) -&gt; Generator[str, None, None]:
    for root, branches in tree.items():
        try:
            yield from implode(branches, (*previous, root))
        except AttributeError:
            yield "".join((*previous, root, *branches))


'* I find i, j etc acceptable for a counter or index, and x and y for coordinates, but in general I try not to use one-letter variable names.