21. April 2015 14:12:51 CEST
Ich habe Aufgabe 3 etwas anders gelöst.
Ein Teilstring y, der Teilstring x enthält, kann nicht häufiger vorkommen als x, dass er genau so häufig ist, ist allerdings möglich.
Ich habe auch einen Baum genutzt, der einen leeren Teilstring als Wurzel hat. Die Kindknoten in diesem Baum haben genau ein Zeichen mehr als ihre Elternknoten, dieses zusätliche Zeichen wird einfach am Ende eingefügt. Dadurch, dass einfach nur ein Zeichen am Ende mehr vorhanden ist, kann der Teilstring nicht häufiger vorkommen als der Elternknoten. Wenn also schon der Kindknoten das Kriterium nicht erfüllt, dass er mindestens k-mal vorkommt, wird besagter Kindknoten gelöscht. Ein Knoten, der daher nur Nachfolger hat, die weniger als k-mal vorkommen, ist daher ein Blatt. Der Baum wird auf diese Weise auf alle Teilstrings beschränkt, die dieses Kriterium erfüllen.
Ob der Teilstring lang genug ist, wird ganz einfach durch auszählen der Zeichen ermittelt.
Alle Teilstrings, die widerlegen könnten, dass der Teilstring maximal ist, müssen am Anfang oder am Ende des Teilstrings mindestens ein Zeichen mehr haben und genau so häufig vorkommen. Die Kindknoten sind solche Teilstrings. Wenn also ein Kindknoten genau so häufig vorkommt, ist der Elternknoten nicht maximal. Die anderen Teilstrings haben ein weiteres Zeichen am Anfang. Auch sie müssen ausgezählt werden. Sollte einer von ihnen genau so häufig vorkommen, ist der Teilstring nicht maximal.
Der Baum in meiner Lösung existiert jedoch nie vollständig, sondern wird rekursiv abgesucht, sodass immer nur der Weg von der Wurzel bis zum aktuell untersuchten Knoten existiert.
Beim Auszählen der Häufigkeit eines Teilstrings wird nur an den Stellen gesucht, an denen der Teilstring auch existieren kann. Wenn z.B. Teilstring y den Teilstring x enthält und man bereits weiß, wo x sich befindet, sucht man eben nur dort.
Für die e-coli sequenz bei k = 2 und l = 2 benötigt das Programm ca. 15 Sekunden und findet 54540 Teilstrings.
