前缀树

可以快读知道有多少以某个字符串作为前缀O(m)
可以快速知道有没有某个字符串O(m)

点的数据结构

class TrieNode():
    def __init__(self):
        self.pas = 0    # 通过了多少次，沿途pas加加
        self.end = 0    # 是否是尾结点，值表示几个结尾，末尾end++
        self.nexts = [None] * 26    # i位表示有没有去i位的路

实现代码

class Trie():
    root = TrieNode()   # 头结点
    # 插入结点方法
    def insert(self,word):
        if word == None:
            return
        node = self.root    # 从根结点出发
        node.pas += 1
        for s in word:
            index = ord(s) - 97     # 减字符a的asc码值
            if node.nexts[index] == None:
                node.nexts[index] = TrieNode()
            node = node.nexts[index]
            node.pas += 1       # 沿途pas++
        node.end += 1           # 最后end++
        
    # 结点查询，查询字符串加入过几次
    def search(self,word):
        if word == None:
            return
        node = self.root    # 根结点出发
        for s in word:      # word遍历一遍
            index = ord(s) - 97
            if node.nexts[index] == None:   # 只要没路了，直接返回0
                return 0
            node = node.nexts[index]
        return node.end
        
    # 加入的字符串中，有几个是以某字符串作为前缀的
    def prefixNumber(self,pre):
        if pre == None:
            return 0
        node = self.root
        for s in pre:
            index = ord(s) - 97
            if node.nexts[index] == None:
                return 0
            node = node.nexts[index]
        return node.pas                 # 返回结果的pas值
        
    # 删除加入的某个字符串
    def delete(self,word):
        if self.search(word) == 0:      # 如果没有加入过这个字符串，则不存在删除
            return
        node = self.root
        node.pas -= 1
        for s in word:
            index = ord(s) - 97
            node.nexts[index].pas -= 1
            if node.nexts[index].pas == 0:  # 下级结点减到0之后，就可以直接放弃了
                node.nexts[index] = None
                return
            node = node.nexts[index]
        node.end -= 1                       # 最后一个结点end--

贪心算法