Wiederkehrende Patterns in einem Text finden

[Gausi]

NP-vollständig würde ich nicht behaupten. Mein Ansatz löst auf den ersten Blick das Problem in Zeit O(N^2). Allerdings komprimiere ich nicht den Text, sondern -äh- expandiere(?) ihn. In meinem Baum speichere ich nur einzelne Zeichen, keine Muster. Muster bekomme ich aus Wegen in diesem Baum. Wenn man Muster suchen möchte, die z.B. mindestens dreimal im Text vorkommen, dann muss man die Wege nehmen, die an der Wurzel starten und Kantenwerte von mindestens 2 haben. Also anschaulich "die dicken Äste" in dem Baum. Oder übersehe ich da grade was? :gruebel:

Anschließend nen Multi-Pattern-Matcher drüberlaufen lassen, die iirc eine Zeitkomplexität von O(n*p) haben, wobei p die Gesamtlänge aller Muster ist. (p kann natürlich maximal n^2 werden, aber das dürfte in realen Texten nie passieren.)