Generalize BDDs to multiway decision diagrams: instead of binary trees on 0 and 1, make n-ary trees on a bigger alphabet. (You probably want to represent the nodes sparsely, not |alphabet| pointers in every node.)

This can directly represent a regex with | operators but not Kleene star. The DD canonicalization automatically makes this structure share suffixes, but not prefixes.