[PYTHON] Ruft die längste Zeichenlänge ab, die in einem Intervall in einem Segmentbaum enthalten ist

Da geschrieben wurde, dass der Segmentbaum verschiedene Aufgaben ausführen kann, je nachdem, was Sie darauf setzen, habe ich das implementiert, was ich mir ausgedacht habe. Es ist an verschiedenen Stellen geschrieben, dass man sich etwas ausdenken muss, um es anzuziehen, aber es war ein gutes Beispiel, also habe ich es gepostet.

Was kann erreicht werden

Vermutetes Problem

Ich möchte die folgenden Fragen mit hoher Geschwindigkeit beantworten.

--Gegeben Sie die n-Zeichenfolge s. s wird ausgedrückt als $ s_ {1}, s_ {2} \ dots s_ {n} $ vom ersten Zeichen.

  1. Schreiben Sie set (i, x) $ s_ {i} $ auf den Buchstaben x um.
  2. Beantworten Sie die Anzahl von "a", die im Intervall von "getCount (s, t)" $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $ enthalten ist.
  3. Beantworten Sie den Maximalwert der Anzahl aufeinanderfolgender a im Intervall $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $ getLongestLen (s, t) $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $.
  4. Beantworten Sie das Intervall "getLeftLen (s, t)" $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $ "die Anzahl der aufeinanderfolgenden a vom linken Ende"
  5. Beantworten Sie das Intervall "getRightLen (s, t)" $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $ "die Anzahl der aufeinanderfolgenden a vom rechten Ende"

Politik

Implementieren Sie einen Segmentbaum, der die folgenden Informationen zu jedem Knoten enthält. (char, count, leftLen, rightLen, longestLen, noneCount)

Ein Beispiel ist oben gezeigt. char: Enthält Zeichen (in der Abbildung nicht vorhanden) count: Nummer von a (5) leftLen: Anzahl aufeinanderfolgender a vom linken Ende der Zeichenfolge (1) rightLen: Anzahl aufeinanderfolgender a vom rechten Ende der Zeichenfolge (2) longLen: Maximale Länge von a im Intervall (kann leftLen oder rightLen sein) (3) noneCount: Summe von noneCount von L und R (in der Abbildung nicht vorhanden) Wird sein. Die Notwendigkeit von noneCount wird später erläutert.

Werteinstellung 1. Über set (i, x)

Weil es ein Wert von höchstens einem Zeichen ist

Grundlagen der Aktualisierung des übergeordneten Knotens

Zunächst wird die Grundoperation beschrieben. Im Folgenden sind L und R die linken untergeordneten Knoten des Knotens und R ist der rechte untergeordnete Knoten. Es gibt einige wichtige Ausnahmen zu (*), die später beschrieben werden.

count: Summe der L- und R-Zählungen leftLen: Übernimm die leftCount des L-Knotens () rightLen: Übernimm die rechte Anzahl des R-Knotens () longLen: Maximalwert (eigene leftLen, eigene rightLen, L rightLen + r leftLen, L längste, R längste) noneCount: Summe von noneCount von L und R.

Hier ist die Berechnung von longLen das Maximum einiger Werte. Erstens ist es selbstverständlich, dass die "längsten Len" für L und R Kandidaten sind. Für L rightLen + r leftLen werden im übergeordneten Knoten das rechte Ende von L und das linke Ende von R verkettet, sodass dies fortlaufende Zeichenfolgen sind und die längsten Kandidaten sind.

Danach werden die folgenden zwei Muster für die kontinuierliche Längenverarbeitung von "leftLen" und "rightLen" beschrieben, wobei angegeben wurde, dass es einen Sonderfall * gibt.

Grundmuster: Zählen von Zeichenfolgen von der Kante und Verarbeiten der rechten Kante einer Zeichenfolge, die kein Leistungsfaktor von 2 ist.

Die Anzahl der Zeichenfolgen von einem Ende ist speziell. Wenn alle Knoten darunter aufeinanderfolgend sind, hat dieses Ende eine fortlaufende Zeichenfolge, die am anderen Ende hinzugefügt wird. Es werden zwei Beispiele gezeigt, und Beispiel 2 entspricht diesem. --Beispiel 1: "aabc" + "aaxz" = "aabcaaxz": Die fortlaufende Zeichenfolge vom rechten Ende ist dieselbe wie L 2, und das linke Ende ist ebenfalls 0. --Beispiel 2: "aaaa" + "aaxz" = "aaaaaaxz": Das linke Ende ist ebenfalls 0, aber da das rechte Ende nur a ist, ist es mit dem linken Ende von R und "L Stringlänge + linkes Ende von R" verbunden Wird sein. Dies ist die Grundlage für die Zeichenfolgenzählung von der Kante.

Aufgrund der Eigenschaften des Segmentbaums sind in der Abbildung die Probleme dargestellt, die während der Initialisierung eindeutig auftreten.

Im Segmentbaum wird die Länge der Zielliste grundsätzlich auf die Zweierpotenz ausgerichtet und gespeichert. Wenn Sie die 7 Zeichen "axbaaaa" wie oben speichern, ist der rechte Rand leer. Dieses Mal wird davon ausgegangen, dass None gespeichert ist. Zu diesem Zeitpunkt, wenn Knoten 6 einen Wert von Knoten 7 und 8 empfängt, hat 8 keinen Wert, so dass die fortlaufende Zeichenfolge auf der rechten Seite als 0 behandelt wird. Daher wird noneCount verwendet.

Die Implementierung erfolgt wie folgt. Für die nachfolgenden "betrachteten Fälle" wird die noneCount-Verarbeitung (Auffüllen) sowohl am rechten als auch am linken Ende hinzugefügt.

    def funcSegmentValue(self, lNode, rNode, parentNodeId):
        lchar, lcnt, lconsLeft, lconsRight, lconsLen, lNoneNum= lNode
        rchar, rcnt, rconsLeft, rconsRight, rconsLen, rNoneNum = rNode

        # l,Gesamtanzahl der in r enthaltenen Zeichen
        ncnt = lcnt + rcnt

        #Die rechte Länge nach der Verkettung stimmt im Wesentlichen mit der linken überein
        nconsLeft = lconsLeft
        nconsRight = rconsRight

        #Auch wenn die Anzahl der aufeinanderfolgenden Zeichenfolgen am linken Ende des rechten Knotens beim Addieren der rechten Knoten nicht ausreicht
        #Wenn Sie die Auffüllung erfüllen, fügen Sie sie der Anzahl aufeinanderfolgender Zeichenfolgen am rechten Ende des linken Knotens hinzu
        #print("magic = {0}".format(2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length()))))

        if lconsLeft == (2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())) - lNoneNum):
            nconsLeft += rconsLeft
        if rconsRight == (2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())) - rNoneNum):
            nconsRight += lconsRight


        nconsLen = max(nconsLeft, nconsRight, lconsLen, rconsLen, lconsRight + rconsLeft)

        nNoneNum = lNoneNum + rNoneNum
        res = [nchar, ncnt, nconsLeft, nconsRight, nconsLen, nNoneNum]
        return res

Zu berücksichtigende Fälle: Verarbeitung auf der linken Seite bei Abfragen

Betrachten Sie nun die Abfrage $ [1,4) $ im 4-stelligen "aaab".

Da der übergeordnete Knoten von "aa" für das Intervall [0,1] verantwortlich ist, fragt er die untergeordneten Knoten des Intervalls 0,1 (in diesem Fall den Blattknoten) ab. Da zu diesem Zeitpunkt der Knoten des Blattes von Abschnitt 0 nicht im Bereich enthalten ist, wird beantwortet, dass der Bereich (in diesem Fall 1) die Antwortlast (= Keine) ist.

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b)Zum Knoten Knoten für die übergeordnete Abfrage des Intervalls[l, r)Liefern Sie die Suche nach
Für das Intervall ist der Index der Daten 0,1,2,3,Wenn es 4 ist,
        [0,3)Dann 0,1,Gibt das Ergebnis von 2 zurück
Bedingung ist Keine: r <= a or b <= l
        """
        if (r <= a or b <= l):
            cannotAnswer = (r - l)
            return [None, 0, 0, 0, 0, cannotAnswer]

        if a <= l and r <= b:
            res =  self.dat[nodeId]
            return res

        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        res = self.funcSegmentValue(resLeft, resRight, nodeId)
        return res

Ganzer Code

#Vom Zielcharakter
#Nur eine Nummer,Anzahl aufeinanderfolgender rechts,Anzahl der aufeinanderfolgenden verbleibenden,Fortlaufende Nummer, (Vom Ende angenommen)Anzahl aufeinanderfolgender Keine
#Anzahl
# cons: consecutive
#Daten sind
# char=Daten enthalten, cnt, consLeft, consRight, consLen,Anzahl noneNum
class segmentTreeCharCount():
    dat = []
    lenTreeList = -1
    targetChar = None
    depthTreeList = 0
    lenPaddingEntry = 0
    unitDefault = [None, 0, 0, 0, 0, 1]

    def __init__(self):
        pass

    def load(self, l, tc):
        self.targetChar = tc
        # len(l)Holen Sie sich das Quadrat von 2 größer als die Zahl
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  #2 für len 5^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length() #Anzahl der Holzstufen(0 origin)
        #lenPaddingEntry ist[1,2,3,4,5]Wenn du gibst[1,2,3,4,5,None,None,None]3 zurückgegeben, da es als behandelt wurde
        self.lenPaddingEntry = 2 ** (len(l) - 1).bit_length() - len(l) #Wie viele Einträge wurden abgeschlossen

        self.dat = [self.unitDefault] * (self.lenTreeList * 2)
        #Wert laden
        for i in range(len(l)):
            if l[i] == self.targetChar:
                self.dat[self.lenTreeList - 1 + i] = [l[i], 1, 1, 1, 1, 0]
            else:
                self.dat[self.lenTreeList - 1 + i] = [l[i], 0, 0, 0, 0, 0]
        self.build()

    def funcSegmentValueById(self, nodeId):
        l = self.dat[nodeId * 2 + 1]
        r = self.dat[nodeId * 2 + 2]
        return self.funcSegmentValue(l, r, nodeId)

    #Führen Sie die Berechnung durch, um zu schreiben.
    #In diesem Fall wird bei dieser Berechnung die Grenze verwendet.,r Position a,Durch Einfügen von b wird das Auffüllen am rechten und am linken Ende durchgeführt.
    def funcSegmentValue(self, lNode, rNode, parentNodeId):
        #print("funcSegmentValue parentNode={0}".format(parentNodeId))
        #print("L:")
        lchar, lcnt, lconsLeft, lconsRight, lconsLen, lNoneNum= lNode
        #print(lNode)
        #print("R:")
        rchar, rcnt, rconsLeft, rconsRight, rconsLen, rNoneNum = rNode
        #print(rNode)

        #Der Einfachheit halber hier umbenannt(Es bedeutet nicht viel)
        if lchar is None or rchar is None:
            nchar = None
        elif rchar is not None:
            nchar = rchar
        elif lchar is not None:
            nchar = lchar

        # l,Gesamtanzahl der in r enthaltenen Zeichen
        ncnt = lcnt + rcnt

        #Die rechte Länge nach der Verkettung stimmt im Wesentlichen mit der linken überein
        nconsLeft = lconsLeft
        nconsRight = rconsRight

        """
        #print("searchdepth = {0}".format(self.depthTreeList - ((parentNodeId + 1).bit_length() - 1)))
        if lcnt == 2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())):
            #print("child!L!")
            nconsLeft += rconsLeft
        if rcnt == 2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())):
            #print("child!R!")
            nconsRight += lconsRight
        """

        #Im Fall von root, selbst wenn die Anzahl der aufeinanderfolgenden Zeichenfolgen am linken Ende des rechten Knotens beim Addieren der rechten Knoten nicht ausreicht
        #Wenn Sie die Auffüllung erfüllen, fügen Sie sie der Anzahl aufeinanderfolgender Zeichenfolgen am rechten Ende des linken Knotens hinzu
        #print("magic = {0}".format(2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length()))))

        if lconsLeft == (2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())) - lNoneNum):
            #print(" parentnodeid {2} l root special cur={0} add={1}".format(nconsRight, rconsLeft, parentNodeId))
            nconsLeft += rconsLeft
        if rconsRight == (2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())) - rNoneNum):
            #print(" parentnodeid {2} r root special cur={0} add={1}".format(nconsRight, rconsLeft, parentNodeId))
            #print(" nconsRight{0} += lconsLeft{1}".format(nconsRight, lconsLeft))
            nconsRight += lconsRight

        #print("update n={0}, max({1},{2},{3},{4},{5}".format(parentNodeId, nconsLeft, nconsRight, lconsLen, rconsLen, lconsRight + rconsLeft))

        nconsLen = max(nconsLeft, nconsRight, lconsLen, rconsLen, lconsRight + rconsLeft)

        nNoneNum = lNoneNum + rNoneNum
        res = [nchar, ncnt, nconsLeft, nconsRight, nconsLen, nNoneNum]
        #print("Return{0}".format(res))
        return res

    # char=Daten enthalten, cnt, consLeft, consRight, consLen
    def build(self):
        for nodeId in range(self.lenTreeList - 2, -1, -1):
            #Wichtig: Dieser Code generiert die Liste neu, ersetzen Sie sie also durch eine Zuweisung!
            self.dat[nodeId] = self.funcSegmentValueById(nodeId)

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        #print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        #print(" first nodeId: {0}".format(nodeId))
        """
        self.dat[nodeId] = a
        if a == self.targetChar:
            self.dat[self.lenTreeList - 1 + i] = [a, 1, 1, 1, 1, 0]
        else:
            self.dat[self.lenTreeList - 1 + i] = [a, 0, 0, 0, 0, 0]
        """
        #print("before")
        #print(self.dat[nodeId])
        self.dat[nodeId] = a
        if a == self.targetChar:
            self.dat[nodeId] = [a, 1, 1, 1, 1, 0]
        else:
            self.dat[nodeId] = [a, 0, 0, 0, 0, 0]
        #print("after")
        #print(self.dat[nodeId])


        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            #print(" next nodeId: {0}".format(nodeId))
            # sum : self.dat[nodeId] = self.dat[nodeId * 2 + 1] + self.dat[nodeId * 2 + 2]
            self.dat[nodeId] = self.funcSegmentValueById(nodeId)

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b)Zum Knoten Knoten für die übergeordnete Abfrage des Intervalls[l, r)Liefern Sie die Suche nach
Für das Intervall ist der Index der Daten 0,1,2,3,Wenn es 4 ist,
        [0,3)Dann 0,1,Gibt das Ergebnis von 2 zurück
Bedingung ist Keine: r <= a or b <= l
        """
        #print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))

        if (r <= a or b <= l):
            cannotAnswer = (r - l)
            #print(" > None") #Dies sollte eine unbeantwortbare Nummer zurückgeben
            return [None, 0, 0, 0, 0, cannotAnswer]
        if a <= l and r <= b:
            #print(" > have: {0} [node = {1}]".format(self.dat[nodeId], nodeId))
            #print(" >     : a={0} <= l={1} and r{2} <= b{3}".format(a,l,r,b))
            res =  self.dat[nodeId]
            return res

        #print("querySubcalc: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        #print("querySubend: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        #print(" > L")
        #print("  node{0}: {1}".format(2 * nodeId + 1, resLeft))
        #print(" > R")
        #print("  node{0}: {1}".format(2 * nodeId + 2, resRight))
        #print(resRight)
        res = self.funcSegmentValue(resLeft, resRight, nodeId)
        #print(" > res")
        #print(res)
        return res

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

    def debugGetSliceStr(self, a, b):
        """
Von der ursprünglichen Stringliste[a:b]Gib es zurück: str
        """
        return "".join(list(map(lambda x: x[0], self.dat[self.lenTreeList - 1 + a:self.lenTreeList - 1 + b])))


from pprint import pprint



def test1(a,b):
    pprint(st.query(a, b))
    pprint(st.debugGetSliceStr(a, b))


l = list("xaazaaa")
l = list("xaaaaa0A")
l = list("abaaabcaaaaxasaaa")
st = segmentTreeCharCount()
st.load(l, "a")
st.build()
#st.setValue(2, "x")
#st.setValue(4, "x")
#print("-----")
#pprint(st.dat)

print("----------------------------")
test1(0,9)
st.setValue(1, "a")
test1(0,9)
st.setValue(0, "x")
st.setValue(1, "x")
st.setValue(2, "x")
st.setValue(3, "x")
st.setValue(8, "x")
test1(0,9)

Recommended Posts

Ruft die längste Zeichenlänge ab, die in einem Intervall in einem Segmentbaum enthalten ist
Rufen Sie die Formel in der Excel-Datei als Zeichenfolge in Python ab
[Python] Holen Sie sich die Dateien mit Python in den Ordner
Im Chainer-Tutorial wird beim Importieren eines Pakets eine Fehlermeldung angezeigt. (spotten)
Holen Sie sich den Aufrufer einer Funktion in Python
Holen Sie sich nur Unterklassenelemente in eine Liste
Erstellen Sie einen Filter, um ein Zugriffstoken mit der Graph-API (Flask) zu erhalten.
Ermitteln Sie die n-kleinste Zahl aus dem Array mit O (logN) mithilfe eines Segmentbaums
Ruft den Variablennamen der Variablen als Zeichenfolge ab.
Abrufen des Dateinamens in einem Ordner mithilfe von glob
Holen Sie sich die Anzahl der spezifischen Elemente in der Python-Liste
So erhalten Sie den letzten (letzten) Wert in einer Liste in Python
So erhalten Sie alle möglichen Werte in einem regulären Ausdruck
Löschen Sie ein bestimmtes Zeichen in Python, wenn es das letzte ist
So ermitteln Sie die Scheitelpunktkoordinaten eines Features in ArcPy
Erstellen Sie eine Funktion, um den Inhalt der Datenbank in Go abzurufen
Sehen Sie sich die in Python 3.8.2 integrierte Ausnahmebaumstruktur an
[Golang] Überprüfen Sie, ob eine bestimmte Zeichenfolge in der Zeichenfolge enthalten ist
Holen Sie sich die Anzahl der Leser von Artikeln über Mendeley in Python
Ich erhalte eine Fehlermeldung, wenn ich ein Python-Plug-In in Visual Studio Code in die pyenv-Umgebung einfüge