Wie implementiert man einen Algorithmus zur Lösung dieser Hausaufgaben in O (n) Zeit von Suffix-Baum?

Question

Ich habe eine Frage in Bioinformatik. Sie können es durch Suffix-Baumstruktur lösen.

Mit einer gegebenen Zeichenkette S = S [1 ... n] und einer Zahl k wollen wir die kleinste Teilkette von S finden, die in S genau k mal vorkommt, falls sie existiert. Wie löst man dieses Problem in O (n) Zeit?

Answer 1

Erstellen Sie den Suffixbaum der Zeichenfolge O (N).

Zähle für jeden Knoten die Anzahl der Blätter darunter O (N).

Suchen Sie einen Knoten, wo die count == k. Der Pfad von der Wurzel zu diesem Knoten ist eine Teilzeichenkette, die genau k mal wiederholt wird.