The original Kleene Star Regex was invented to model neural networks. Have you tried throwing a transformer at the problem /s? Also O(n²) but at least you get hardware acceleration ¯\(ツ)/¯

Here's Kleene's Representation of Events in Nerve Nets and Finite Automata:

https://www.rand.org/content/dam/rand/pubs/research_memorand...