wenn die regulären ausdrücke so einfach sind wie die oben, dann kannste auch mal versuchen, mit einem Trie zu arbeiten.
zufällig gibts da was aufm cpan ;)

du müsstest die regulären ausdrücke in die wortmengen auflösen (da hab ich leider nur eines gefunden, was den umgekehrten weg geht). die wörter dann in den trie einbetten. der trie sorgt dann von sich aus für die prefix-beziehung.