Wenn der String Länge , kann das Ermitteln der Anzahl unterschiedlicher Teilzeichenfolgen in linearer Zeit unter Verwendung eines LCP-Arrays erfolgen. Anstatt nach der Anzahl der eindeutigen Teilzeichenfolgen in der gesamten Zeichenfolge fragen, fragt die Abfrage mit der Indizierung wobei nach der Anzahl der unterschiedlichen Teilzeichenfolgen innerhalb des angegebenen für die Zeichenfolge .
Mein Ansatz besteht darin, auf jede Abfrage eine lineare Zeitkonstruktion des LCP-Arrays anzuwenden. Es ergibt die Komplexität . Die Anzahl der Abfragen kann auf die Reihenfolge erhöht werden. also alle Abfragen beantworten, wird .
Kann es besser gemacht werden als die lineare Zeit für jede Abfrage?
Wenn ein Prozess-Teilstring eines Strings, für den wir bereits ein Suffix-Array, einen Suffix-Baum oder ein lcp-Array haben, im Allgemeinen nicht mehr relevant ist und erneut von Grund auf neu erstellt werden muss?
quelle
Antworten:
Die Frage motiviert nicht dazu, dass die Anzahl der Abfragen , was ein willkürlich schlechtester Fall zu sein scheint, da die Anzahl der eindeutigen möglichen Abfragen die Anzahl der geordneten Paare und damit .O(n) O(n2)
Hier sind zwei verschiedene Lösungen mit besserer Zeitkomplexität für den Fall basierend auf (impliziten) Suffixbäumen, die schrittweise mit dem Ukkonen-Algorithmus erstellt wurden . Beide Lösungen basieren auf der Vorverarbeitung und haben die Komplexität wobei die Menge der Abfragen ist. Die zweite Lösung wird in wenn alle Abfragen dieselbe Breite haben.O(n2) O(n2+|Q|) Q O(n+|Q|)
Lösung 1 - Verarbeiten Sie alle eindeutigen Abfragen vor
Iterate über die Suffixe von . für jedes Suffix den Suffixbaum von mit dem Ukkonen-Algorithmus. Speichern Sie nach der Aktualisierung von auf den aktuellen Suffixbaum die Baumgröße in einer Matrix an Position . Eine Abfrage nach dem Bereich wird vom Matrixelement bei beantwortet .S Si=S[i..n] Si j (i,i+j−1) [x,y] (x,y)
Die Suffixbaumgröße kann zusammen mit dem Suffixbaum gespeichert und bei jedem Schritt in konstanter Zeit aktualisiert werden, indem die Aktualisierungsprozedur im Ukkonen-Algorithmus geändert wird. Mit jedem Update erhöht sich die Größe um die aktuelle Anzahl der Blätter.
Lösung 2 - Verarbeiten Sie eindeutige Abfragebreiten vor
Diese Lösung ist schwieriger zu implementieren, erfordert jedoch weniger Vorverarbeitungsarbeit, wenn nur wenige Abfragebreiten vorhanden sind. Die Vorverarbeitung benötigt Zeit, wenn nur eine Abfragebreite vorhanden ist.O(n)
Verwenden Sie für jede Abfragebreite ein Schiebefenster mit der Breite und erstellen Sie schrittweise einen Suffixbaum. Entfernen Sie das Suffix ab einem Zeichen links vom Fenster, indem Sie das längste Suffix aus dem Baum entfernen. Bei jedem Schritt entspricht die aktuelle Anzahl der Teilzeichenfolgen innerhalb des Schiebefensters der Baumgröße.w w
Alle Anfragen können dann unter Verwendung der Ergebnisse der Vorberechnung in linearer Zeit beantwortet werden.
Hinweis: Das Entfernen des längsten Suffix kann durch Entfernen des ältesten Blattes des Suffixbaums erfolgen. Die korrekte Implementierung ist nicht einfach.
quelle
Es gibt eine Offline-Lösung .O(nn−−√+|Q|n−−√)
Schritt 3 nimmt für jeden Bucket, da wir den Ukkonen-Algorithmus verwenden und in aufsteigender Reihenfolge abläuft .O(n) j
Schritt 4 benötigt für jede Abfrage, da das Entfernen der längsten Suffixe von aus dem Baum . Beachten Sie, dass Sie eine Indirektionsebene verwenden können, um Änderungen am ursprünglichen Suffixbaum zu vermeiden.O(n−−√) n−−√ O(n−−√)
quelle