[PYTHON] Obtenir la longueur de caractère la plus longue contenue dans un intervalle dans une arborescence de segments

Depuis qu'il a été écrit que l'arborescence des segments peut faire différentes choses en fonction de ce que vous y mettez, j'ai implémenté ce que j'ai proposé. Il est écrit à divers endroits que vous devez imaginer quelque chose à mettre, mais c'était un bon exemple, alors je l'ai affiché.

Ce qui peut être réalisé

--Initialisation: $ O (N) $

Problème supposé

Je veux répondre rapidement aux questions suivantes.

  1. Réécrivez set (i, x) $ s_ {i} $ à la lettre x.
  2. Répondez au nombre de ʻacontenu dans l'intervallegetCount (s, t)` $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $.
  3. Répondez à la valeur maximale du nombre de a 'consécutifs dans l'intervalle $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} ` getLongestLen (s, t) ` s_ {s}, s_ {s + 1}, \ dots, s_ {t} $.
  4. Répondez à getLeftLen (s, t) $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $ interval le nombre de a consécutifs à partir de l'extrémité gauche
  5. Répondez à getRightLen (s, t) $ s_ {s}, s_ {s + 1}, \ dots, s_ {t} $ interval le nombre de a consécutifs de l'extrémité droite

politique

Implémentez une arborescence de segments qui porte les informations suivantes sur chaque nœud. (char, count, leftLen, rightLen, longestLen, noneCount)

Un exemple est présenté ci-dessus. char: contient des caractères (non présents sur la figure) count: nombre d'un (5) leftLen: Nombre de a consécutifs à partir de l'extrémité gauche de la chaîne (1) rightLen: Nombre de a consécutifs à partir de l'extrémité droite de la chaîne (2) longestLen: longueur maximale de a dans l'intervalle (peut être leftLen ou rightLen) (3) noneCount: somme de noneCount de L et R (non présent sur la figure) Sera. La nécessité de noneCount sera expliquée plus tard.

Réglage de la valeur 1. À propos de l'ensemble (i, x)

Parce que c'est une valeur d'au plus un caractère --Lorsque x = a (" a ", 1, 1, 1, 1, 0) --x = Sinon (<char>, 0, 0, 0, 0, 0) Et l'extrémité droite à remplir lors de la création d'un arbre de segmentation est (Aucun, 0, 0, 0, 0, 1).

Principes de base de la mise à jour du nœud parent

Tout d'abord, le fonctionnement de base sera décrit. Ci-après, L et R sont les nœuds enfants gauches du nœud, et R est le nœud enfant droit. Il existe quelques exceptions importantes à (*), qui seront décrites plus loin.

count: somme des comptes L et R leftLen: Reprend le leftCount du nœud L () rightLen: Reprend le rightCount du nœud R () longestLen: Valeur maximale (propre leftLen, own rightLen, L rightLen + r leftLen, L plus long, R Longest) noneCount: somme de noneCount de L et R

Ici, le calcul de «longestLen» est la valeur maximale de certaines valeurs. Premièrement, il va de soi que les «Len les plus longs» pour L et R sont des candidats. Pour L rightLen + r leftLen, dans le nœud parent, l'extrémité droite de L et l'extrémité gauche de R sont concaténées, ce sont donc des chaînes de caractères continues et sont les candidats les plus longs.

Après cela, les deux modèles suivants seront décrits pour le traitement de la longueur continue de "leftLen" et "rightLen", ce qui indique qu'il existe un cas spécial *.

Modèle de base: compter les chaînes à partir du bord et traiter le bord droit d'une chaîne qui n'est pas un facteur de puissance de 2.

Le nombre de chaînes à une extrémité est spécial, «si tous les nœuds en dessous sont consécutifs a», cette extrémité a une chaîne continue qui est ajoutée à l'autre extrémité. Deux exemples sont présentés, et l'exemple 2 correspond à cela.

Ensuite, en raison des caractéristiques de l'arborescence de segments, les problèmes qui se produisent clairement lors de l'initialisation sont indiqués sur la figure.

Dans l'arborescence de segments, la longueur de la liste cible est essentiellement alignée sur la puissance de 2 et stockée. Si vous stockez les 7 caractères "axbaaaa" comme ci-dessus, le bord droit sera vide. Cette fois, on suppose que None est stocké. À ce stade, lorsque le nœud 6 reçoit une valeur des nœuds 7 et 8, 8 n'a pas de valeur, donc la chaîne de caractères continue sur le côté droit est traitée comme 0. Par conséquent, noneCount est utilisé.

--Lorsque le nœud 6 reçoit une valeur du nœud 8, cette longueur d'intervalle 1 --noneCount value 1 = 0 est incluse, donc définissez rightLen sur 0 + 2 (rightLen de L).

La mise en œuvre de ceci est la suivante. Pour les "cas considérés" suivants, le traitement noneCount (remplissage) est ajouté aux extrémités droite et gauche.

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

        # l,Nombre total de caractères contenus dans r
        ncnt = lcnt + rcnt

        #La bonne longueur après concaténation correspond essentiellement à la gauche
        nconsLeft = lconsLeft
        nconsRight = rconsRight

        #Même si le nombre de chaînes de caractères consécutives à l'extrémité gauche du nœud droit est insuffisant lors de l'addition des nœuds droits
        #Si vous rencontrez le remplissage, ajoutez-le au nombre de chaînes consécutives à l'extrémité droite du nœud gauche
        #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

Cas à considérer: traitement à gauche lors de l'interrogation

Considérons maintenant la requête $ [1,4) $ dans le "aaab" à 4 caractères.

Puisque le nœud parent de "aa" est en charge de l'intervalle [0,1], il interroge les nœuds enfants de l'intervalle 0,1 (dans ce cas, le nœud feuille). A ce moment, comme le nœud de la feuille de la section 0 n'est pas inclus dans la plage, il est répondu que la plage (1 dans ce cas) est la charge de réponse (= Aucune).

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b)Au nœud de nœud pour la requête parente de l'intervalle[l, r)Livrer la recherche pour
Pour l'intervalle, l'indice des données est 0,1,2,3,Quand il est 4,
        [0,3)Puis 0,1,Renvoie le résultat de 2
Condition à aucune: 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

Code entier

#Du personnage cible
#Juste un chiffre,Nombre de consécutifs à droite,Nombre de restants consécutifs,Numéro consécutif, (Assumé depuis la fin)Nombre de consécutifs Aucun
#Compter
# cons: consecutive
#les données sont
# char=Données incluses, cnt, consLeft, consRight, consLen,Nombre de 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)Obtenez le carré de 2 plus grand que le nombre
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  #2 pour len 5^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length() #Nombre d'étapes de bois(0 origin)
        #lenPaddingEntry est[1,2,3,4,5]Si vous donnez[1,2,3,4,5,None,None,None]Renvoyé 3 car il a été traité comme
        self.lenPaddingEntry = 2 ** (len(l) - 1).bit_length() - len(l) #Combien d'entrées ont été complétées

        self.dat = [self.unitDefault] * (self.lenTreeList * 2)
        #Valeur de charge
        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)

    #Faites le calcul pour écrire.
    #Dans ce cas, la frontière est utilisée dans ce calcul.,r position a,En insérant b, un remplissage à l'extrémité droite et à l'extrémité gauche est effectué.
    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)

        #Renommé ici pour plus de commodité(Ça ne veut pas dire grand chose)
        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,Nombre total de caractères contenus dans r
        ncnt = lcnt + rcnt

        #La bonne longueur après concaténation correspond essentiellement à la gauche
        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
        """

        #Dans le cas de la racine, même si le nombre de chaînes de caractères consécutives à l'extrémité gauche du nœud droit est insuffisant lors de l'addition des nœuds droits
        #Si vous rencontrez le remplissage, ajoutez-le au nombre de chaînes consécutives à l'extrémité droite du nœud gauche
        #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=Données incluses, cnt, consLeft, consRight, consLen
    def build(self):
        for nodeId in range(self.lenTreeList - 2, -1, -1):
            #Important: ce code régénérera la liste, alors remplacez-le par une affectation!
            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)Au nœud de nœud pour la requête parente de l'intervalle[l, r)Livrer la recherche pour
Pour l'intervalle, l'indice des données est 0,1,2,3,Quand il est 4,
        [0,3)Puis 0,1,Renvoie le résultat de 2
Condition à aucune: 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") #Cela devrait renvoyer un numéro sans réponse
            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):
        """
De la liste de chaînes d'origine[a:b]rends le: 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

Obtenir la longueur de caractère la plus longue contenue dans un intervalle dans une arborescence de segments
Obtenez la formule dans le fichier Excel sous forme de chaîne en Python
[Python] Récupérez les fichiers dans le dossier avec Python
Dans le tutoriel Chainer, j'obtiens une erreur lors de l'importation d'un package. (moquer)
Récupérer l'appelant d'une fonction en Python
Obtenir uniquement les éléments de sous-classe dans une liste
Créez un filtre pour obtenir un jeton d'accès avec l'API Graph (Flask)
Obtenez le nième plus petit nombre du tableau avec O (logN) en utilisant une arborescence de segments
Obtenez le nom de la variable sous forme de chaîne de caractères.
Obtenir le nom de fichier dans un dossier à l'aide de glob
Obtenez le nombre d'éléments spécifiques dans la liste python
Comment obtenir la dernière (dernière) valeur d'une liste en Python
Comment obtenir toutes les valeurs possibles dans une expression régulière
Supprimer un caractère spécifique en Python s'il s'agit du dernier
Comment obtenir les coordonnées de sommet d'une entité dans ArcPy
Créez une fonction pour obtenir le contenu de la base de données dans Go
Jetez un œil à l'arborescence des exceptions intégrée dans Python 3.8.2
[Golang] Vérifiez si une chaîne de caractères spécifique est incluse dans la chaîne de caractères
Obtenez le nombre de lecteurs d'articles sur Mendeley en Python
J'obtiens une erreur lorsque je mets un plug-in Python dans Visual Studio Code sous l'environnement pyenv