從廣義上來(lái)講：數(shù)據(jù)結(jié)構(gòu)就是一組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 仅仆， 算法就是操作數(shù)據(jù)的方法

數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的器赞，算法是要作用在特定的數(shù)據(jù)結(jié)構(gòu)上的枫绅。

10個(gè)最常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表衡招、棧呜舒、隊(duì)列、散列表瓦堵、二叉樹、堆、跳表贿衍、圖、Trie樹

10個(gè)最常用的算法：遞歸救恨、排序贸辈、二分查找、搜索肠槽、哈希算法擎淤、貪心算法、分治算法秸仙、回溯算法嘴拢、動(dòng)態(tài)規(guī)劃、字符串匹配算法

本文總結(jié)了20個(gè)最常用的數(shù)據(jù)結(jié)構(gòu)和算法寂纪，不管是應(yīng)付面試還是工作需要席吴，只要集中精力攻克這20個(gè)知識(shí)點(diǎn)就足夠了。

數(shù)據(jù)結(jié)構(gòu)和算法（一）：復(fù)雜度捞蛋、數(shù)組孝冒、鏈表、棧拟杉、隊(duì)列的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（二）：遞歸庄涡、排序、通用排序算法的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（三）：二分查找搬设、跳表穴店、散列表、哈希算法的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（四）：二叉樹焕梅、紅黑樹迹鹅、遞歸樹、堆和堆排序贞言、堆的應(yīng)用的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（五）：圖斜棚、深度優(yōu)先搜索和廣度優(yōu)先搜索、字符串匹配算法、Trie樹弟蚀、AC自動(dòng)機(jī)的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（六）：貪心算法蚤霞、分治算法、回溯算法义钉、動(dòng)態(tài)規(guī)劃昧绣、拓?fù)渑判虻膫魉烷T

第二十一章 圖

首先呢，先思考一個(gè)問題捶闸，如何存儲(chǔ)微博夜畴、微信等社交網(wǎng)絡(luò)中的好友關(guān)系呢？

一删壮、什么是圖贪绘？及圖中的幾個(gè)基礎(chǔ)概念

• 1. 圖跟前邊講的樹一樣，也是一種非線性表結(jié)構(gòu)央碟，比樹更加復(fù)雜税灌，樹中的元素我們稱之為節(jié)點(diǎn)，圖中的元素就稱之為頂點(diǎn)亿虽，從下圖可以看出菱涤，圖的頂點(diǎn)可以與任意頂點(diǎn)建立關(guān)系，我們把這種關(guān)系稱之為邊（edge）洛勉。
     
     圖中的頂點(diǎn)和邊
• 2. 我們可以把微信的好友關(guān)系看做一張圖粘秆，其中每個(gè)用戶都可以看做一個(gè)頂點(diǎn)，用戶之間的好友關(guān)系就可以看做邊坯认，每個(gè)用戶有多少好友翻擒，就叫做頂點(diǎn)的度，度就是跟頂點(diǎn)相連接的邊的條數(shù)牛哺。
• 3. 微博中允許單向關(guān)注陋气，也就是用戶A關(guān)注了用戶B，但是用戶B沒有關(guān)注用戶A引润，我們就可以用有向圖巩趁，來(lái)表示這種關(guān)系，如下圖所示淳附，我們把有方向的圖叫做有向圖议慰，沒有方向的圖叫做無(wú)向圖。
     
     有向圖
• 4. 在圖中奴曙，我們把一個(gè)頂點(diǎn)有多少條邊叫做度别凹，如果圖有方向，就把指向頂點(diǎn)的邊數(shù)叫做入度洽糟，從這個(gè)頂點(diǎn)指出去的邊叫做出度炉菲，如下圖所示堕战。對(duì)應(yīng)到微博的例子，入度就表示有多少粉絲拍霜，出度就表示關(guān)注了多少人嘱丢。
     
     度、入度祠饺、出度
• 5. QQ中不但記錄了好友關(guān)系越驻，還記錄了親密度，這種帶親密度的好友關(guān)系道偷，我們可以用帶權(quán)圖來(lái)表示缀旁，如下圖，每條邊都有一個(gè)權(quán)重(weight)勺鸦，可以通過(guò)這個(gè)權(quán)重來(lái)表示QQ中的親密度诵棵。
     
     帶權(quán)圖

二、如何在內(nèi)存中存儲(chǔ)圖祝旷？

方法一：鄰接矩陣法

• 1. 用連續(xù)的內(nèi)存空間存儲(chǔ)圖的方法叫做領(lǐng)接矩陣（Adjacency Matrix），鄰接矩陣的底層是二維數(shù)組嘶窄，對(duì)無(wú)向圖來(lái)說(shuō)怀跛，如果頂點(diǎn)i和頂點(diǎn)j之間有邊，我們就將A[i][j]和A[j][i]標(biāo)記為1柄冲；對(duì)于有向圖來(lái)說(shuō)吻谋，如果頂點(diǎn)i和頂點(diǎn)j之間只有一條從頂點(diǎn)i指向頂點(diǎn)j的邊，就只將A[i][j]標(biāo)記為1现横；對(duì)于帶權(quán)圖來(lái)說(shuō)漓拾，數(shù)組中存放的是響應(yīng)的權(quán)重。如下圖所示：
     
     鄰接矩陣存儲(chǔ)法.png
• 2. 用鄰接矩陣存儲(chǔ)圖戒祠，雖然簡(jiǎn)單直觀骇两，但是比較浪費(fèi)內(nèi)存空間。例如在無(wú)向圖中姜盈，如果A[i][j]等于1低千，那么A[j][i]也一定等于1，我們存儲(chǔ)一個(gè)其實(shí)就夠了馏颂，從對(duì)角線一份為二示血，我們只需要存儲(chǔ)一半就夠了，另一半就浪費(fèi)了救拉。如下圖：
     
     用鄰接矩陣存儲(chǔ)無(wú)向圖有點(diǎn)浪費(fèi)

• 3. 用鄰接矩陣的方法存儲(chǔ)圖难审，相當(dāng)于給所有的頂點(diǎn)之間的關(guān)系都預(yù)留的內(nèi)存，但是如果我們是稀疏圖亿絮，也就是說(shuō)告喊，頂點(diǎn)很多麸拄，但是每個(gè)頂點(diǎn)的邊并不多的時(shí)候，用鄰接矩陣就更加浪費(fèi)了葱绒，例如感帅，微信有好幾個(gè)億的用戶，但是每個(gè)用戶的好友并不多地淀，一般也就幾百個(gè)失球，對(duì)應(yīng)在圖中，就是好幾億個(gè)頂點(diǎn)帮毁，每個(gè)頂點(diǎn)就幾百個(gè)邊实苞，用鄰接矩陣來(lái)存儲(chǔ)的話，絕大部分的空間都被浪費(fèi)了烈疚。
• 4. 也不是說(shuō)鄰接矩陣存儲(chǔ)法完全沒有優(yōu)點(diǎn)黔牵，首先，鄰接矩陣存儲(chǔ)方式簡(jiǎn)單爷肝、直觀猾浦，基于數(shù)組，獲取頂點(diǎn)之間的關(guān)系非常高效灯抛；其次金赦，計(jì)算方便，很多圖的運(yùn)算可以轉(zhuǎn)換成矩陣之間的運(yùn)算对嚼，例如求解最短路徑問題夹抗，就是利用矩陣循環(huán)相乘若干次得到結(jié)果。

方法二：鄰接表存儲(chǔ)法

• 1. 鄰接表的每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表纵竖，鏈表中存儲(chǔ)的是與此頂點(diǎn)有關(guān)系的其他頂點(diǎn)漠烧，如下圖，就是一個(gè)有向圖用鄰接表法存儲(chǔ)的直觀展示靡砌。

     
     
     有向圖用鄰接表存儲(chǔ)
• 2. 相比于鄰接矩陣存儲(chǔ)已脓，鄰接表存儲(chǔ)更節(jié)省內(nèi)存，但是使用起來(lái)比較耗時(shí)乏奥，例如摆舟，想知道頂點(diǎn)2與頂點(diǎn)4之間是否存在關(guān)系，就需要遍歷頂點(diǎn)2所對(duì)應(yīng)的的鏈表邓了。我們也可以仿照前邊處理散列沖突的方式恨诱，來(lái)處理遍歷鏈表所帶來(lái)的的耗時(shí)問題，將鏈表替換成跳表或者紅黑樹骗炉，這樣查找的時(shí)間復(fù)雜度就從O(n)變成了O(logn)了照宝。

三、如何在存儲(chǔ)微博中的社交關(guān)系呢句葵？

• 1. 社交網(wǎng)絡(luò)是一個(gè)稀疏圖厕鹃，用鄰接矩陣法存儲(chǔ)比較浪費(fèi)時(shí)間兢仰，所以應(yīng)該采用鄰接表法來(lái)存儲(chǔ)，但是用一個(gè)鄰接表只能表示用戶關(guān)注了誰(shuí)剂碴，無(wú)法知道粉絲列表把将，所以我們還需要一個(gè)逆鄰接表，來(lái)存放粉絲忆矛，也就是存放指向這個(gè)定向的邊察蹲，如下圖：

     
     
     鄰接表和逆鄰接表
• 2. 用鏈表的話時(shí)間復(fù)雜度是O(n)，所以我們應(yīng)該將鏈表替換成跳表或者紅黑樹等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)催训，由于微博中需要按照用戶首字母排序洽议，所以我們可以使用跳表，跳表的插入漫拭、查找亚兄、刪除的時(shí)間復(fù)雜度都是O(logn)非常高效，同時(shí)跳表中的數(shù)據(jù)都是有序的采驻，分頁(yè)獲取粉絲列表或者關(guān)注列表也很高效审胚。

• 3. 微博擁有好幾億的用戶，一臺(tái)機(jī)器的內(nèi)存肯定是不夠的礼旅，我們可以用過(guò)哈希算法進(jìn)行數(shù)據(jù)分片菲盾，將鄰接表存放到不同機(jī)器上「鞯恚可以這樣處理：對(duì)數(shù)據(jù)進(jìn)行哈希得到哈希值，再用這個(gè)哈希值和機(jī)器總數(shù)取模诡挂，得到機(jī)器編號(hào)碎浇，將這個(gè)數(shù)據(jù)的鄰接表放到這臺(tái)機(jī)器上就可以了。

     
     
     用哈希算法進(jìn)行數(shù)據(jù)分片
• 4. 我們還可以利用外部存儲(chǔ)來(lái)持久化存儲(chǔ)數(shù)據(jù)璃俗，例如使用數(shù)據(jù)庫(kù)奴璃，并建立多級(jí)索引。

第二十二章 深度優(yōu)先搜索和廣度優(yōu)先搜索

一城豁、什么是搜索算法

• 1. 算法是作用在具體數(shù)據(jù)結(jié)構(gòu)上的苟穆，深度優(yōu)先搜索和廣度優(yōu)先搜索算法都是作用于圖這種數(shù)據(jù)結(jié)構(gòu)上的，這是因?yàn)閳D的表達(dá)能力很強(qiáng)唱星，大部分涉及搜索的場(chǎng)景都可以抽象成“圖”雳旅。
• 2. 圖的搜索算法，其實(shí)在圖上找出從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑间聊，今天介紹兩種最簡(jiǎn)單攒盈、最暴力的搜索算法：廣度優(yōu)先搜索（Breadth-First-Search）和深度優(yōu)先搜索（Depth-First-Search）

二、BFS-廣度優(yōu)先搜索（Breadth-First-Search）

• 1. 廣度優(yōu)先搜索哎榴，其實(shí)就是地毯式的層層遞進(jìn)策略型豁，即先查找最近的頂點(diǎn)僵蛛，再找次近的，依次往外搜索迎变，如下圖：

     
     
     廣度優(yōu)先搜索
• 2. 用Swift代碼實(shí)現(xiàn)充尉，如下

//單鏈表
class SingleLinkedList{
    var headNode: SingleLinkedNode?
    var nodeMap: Dictionary<String, SingleLinkedNode>?
    var nodeCount: Int = 0
    
    //插入一個(gè)節(jié)點(diǎn)
    func insertNode(node: SingleLinkedNode){
        nodeMap?.updateValue(node, forKey: node.key)
        nodeCount = nodeCount + 1
        if headNode == nil{
            headNode = node
        }else{
            lastNode().next = node
        }
    }
    
    //獲取一個(gè)節(jié)點(diǎn)
    func lastNode() -> SingleLinkedNode{
        var node = headNode
        while node?.next != nil {
            node = node?.next
        }
        if node != nil{
            return node!
        }else{
            return SingleLinkedNode(key: "error", value: "error")
        }
    }
    
    //根據(jù)key獲取節(jié)點(diǎn)
    func getNode(key: String) -> SingleLinkedNode?{
        return nodeMap?[key]
    }
    
    //刪除node的下一個(gè)節(jié)點(diǎn)
    func deleteNode(_ node: SingleLinkedNode){
        if (nodeMap?[node.key] ?? SingleLinkedNode(key: "", value: "")) == node{
            nodeCount = nodeCount - 1
            node.next = node.next?.next
        }else{
            print("該節(jié)點(diǎn)不存在")
        }
    }
    
    func size() -> Int{
        return nodeCount
    }
}

//單鏈表的節(jié)點(diǎn)
class SingleLinkedNode: Equatable{
    static func == (lhs: SingleLinkedNode, rhs: SingleLinkedNode) -> Bool {
        if lhs.key == rhs.key && lhs.value == rhs.value && lhs.next == rhs.next{
            return true
        }
        return false
    }
    
    var key:String = "-1"
    var value: String?
    var next: SingleLinkedNode?
    init(key: String,value: String) {
        self.key = key
        self.value = value
    }
}

//先入先出的順序隊(duì)列
class Queue<T>{
    private var array: Array<T> = Array()
    //入隊(duì)
    func enqueue(_ e: T){
        array.append(e)
    }
    //出隊(duì)
    func dequeue() -> T?{
        if let first = array.first{
            array.remove(at: 0)
            return first
        }
        return nil
    }
    
    func size() -> Int{
        return array.count;
    }
}

let queue = Queue<Int>()
queue.enqueue(11)
queue.enqueue(2)
queue.enqueue(333)
let testQueue1 = queue.dequeue()
let testQueue2 = queue.dequeue()
let testQueue3 = queue.dequeue()

//無(wú)向圖
class Graph{
    private var peakCount: Int = 0                          //頂點(diǎn)的個(gè)數(shù)
    private var linkedArray = Array<SingleLinkedList>()     //單鏈表的數(shù)組
    
    //初始化
    init(peakCount: Int) {
        self.peakCount = peakCount
        let linkedList = SingleLinkedList()
        self.linkedArray = Array(repeating: linkedList, count: self.peakCount)
    }
    
    //增加一條邊（無(wú)向圖一條邊需要存兩次）
    func addEdge(s: Int,t: Int){
        let nodeT = SingleLinkedNode(key:"\(t)" ,value: "\(t)")
        let nodeS = SingleLinkedNode(key: "\(s)", value: "\(s)")
        linkedArray[s].insertNode(node: nodeT)
        linkedArray[t].insertNode(node: nodeS)
    }
    
    // 廣度優(yōu)先搜索 從頂點(diǎn)開始 尋找到t頂點(diǎn)的路徑 打印出來(lái)
    func bfs(start_s: Int,target_t: Int){
        //如果起點(diǎn)等于重點(diǎn) 直接return
        if start_s == target_t {
            return
        }
        //已經(jīng)訪問過(guò)的頂點(diǎn)
        var visited = Array<Bool>()
        //先入先出的隊(duì)列，負(fù)責(zé)存儲(chǔ)已經(jīng)被訪問過(guò)但其相連的頂點(diǎn)還沒有訪問的頂點(diǎn)
        let queue = Queue<Int>()
        //將第一個(gè)頂點(diǎn)s加入隊(duì)列
        queue.enqueue(start_s)
        //記錄搜索路徑
        var recordSearchPath = Array(repeating: -1, count: peakCount)
        while(queue.size() != 0){
            //當(dāng)前頂點(diǎn)
            let currentPeak = queue.dequeue() ?? 0
            for i in 0..<linkedArray[currentPeak].size(){
                //當(dāng)前頂點(diǎn)所對(duì)應(yīng)的的節(jié)點(diǎn)
                let currentNode = linkedArray[currentPeak].getNode(key: "\(i)")
                //當(dāng)前節(jié)點(diǎn)的位置
                let currentSub = Int(currentNode?.key ?? "0") ?? 0
                if !visited[currentSub]{
                    recordSearchPath[currentSub] = currentPeak
                    if currentSub == target_t{
                        print("找到了")
                        return
                    }
                    visited[currentSub] = true
                    queue.enqueue(currentSub)
                }
            }
        }
    }
}

• 3. 廣度優(yōu)先搜索最壞情況下衣形，終止頂點(diǎn)t與起始頂點(diǎn)s相距很遠(yuǎn)驼侠，需要遍歷整個(gè)圖才能找到，每個(gè)頂點(diǎn)都要進(jìn)隊(duì)列一次泵喘，每條邊也都要被訪問一次泪电，所以廣度優(yōu)先搜索的時(shí)間復(fù)雜度是O(V+E)，V代表頂點(diǎn)數(shù)量纪铺，E代表邊的數(shù)量相速；對(duì)于一個(gè)連通圖來(lái)說(shuō)，圖中的所有頂點(diǎn)都是連通的鲜锚，E肯定大于等于V-1突诬，所以廣度優(yōu)先搜索的時(shí)間復(fù)雜度也可以簡(jiǎn)寫為O(E)，E代表邊數(shù)芜繁。
• 4. 廣度優(yōu)先搜索的空間消耗主要在幾個(gè)輔助變量上旺隙，輔助變量的存儲(chǔ)空間的大小不過(guò)超過(guò)頂點(diǎn)的個(gè)數(shù)，所以空間復(fù)雜度是O(V)骏令，V代表頂點(diǎn)數(shù)蔬捷。

三、DFS-深度優(yōu)先搜索（Depth-First-Search）

• 1. 深度優(yōu)先搜索榔袋，其實(shí)就是走迷宮周拐，你站在岔路口上，選擇一條路往下走凰兑，走著走著發(fā)現(xiàn)走不通了妥粟，就退回到上一個(gè)岔路口，重新選擇一條路繼續(xù)走吏够，按照這種策略勾给，一直走下去，直到找到出口為止锅知。如下圖：

     
     
     深度優(yōu)先搜索策略
• 2. 用Swift代碼實(shí)現(xiàn)播急，如下
• 3. 從上圖中可以看出，按照深度優(yōu)先搜索策略售睹，每條邊最多會(huì)被訪問2次旅择，一次是遍歷，一次是回退侣姆，所以深度優(yōu)先搜索的時(shí)間復(fù)雜度是O(E)生真，E代表邊數(shù)
• 4. 從代碼可以看出沉噩，深度優(yōu)先搜索的內(nèi)存消耗跟頂點(diǎn)的個(gè)數(shù)成正比，所以空間復(fù)雜度為O(V)柱蟀，V代表頂點(diǎn)數(shù)川蒙。

第二十三章 字符串匹配基礎(chǔ)

字符串匹配算法分為單模式串匹配和多模式串匹配。單模式匹配长已，即一個(gè)串和另一個(gè)串進(jìn)行匹配畜眨，例如：BF算法、RK算法术瓮、BM算法康聂、KMP算法；也有多模式串匹配胞四，即在一個(gè)串中同時(shí)查找多個(gè)串恬汁，例如：Tire樹。

一辜伟、BF算法

• 1. BF算法的BF是Brute Force的縮寫氓侧，中文叫做暴力匹配算法，從名字就可以看出导狡，這種算法簡(jiǎn)單约巷、暴力、好懂旱捧，相應(yīng)的性能也不高独郎。
• 2. 這里有兩個(gè)概念必須先弄懂：主串和模式串，我們?cè)谧址瓵中查找字符串B枚赡，A就是主串囚聚，B就是模式串。我們把主串的長(zhǎng)度記為n标锄，模式串長(zhǎng)度記為m，因?yàn)樵谥鞔胁檎夷Ｊ酱录疲鞔隙ū饶Ｊ酱L(zhǎng)料皇，n>m.
• 3. BF的核心思想是：在主串中，檢查起始位置分別是0星压、1践剂、2...n-m且長(zhǎng)度為m的n-m+1個(gè)子串，看有沒有和模式串匹配的娜膘。例如下圖所示
     
     BF核心思想.png
• 4. 極端情況下逊脯，BF需要匹配n-m+1次，每次匹配m個(gè)字符竣贪，所以最壞時(shí)間復(fù)雜度為O(n*m)

二军洼、RK算法

• 1. RK算法的全稱是Rabin-Karp算法巩螃，是BF算法的升級(jí)版，RK算法在BF算法的基礎(chǔ)上匕争，引入了哈希算法避乏，降低了時(shí)間復(fù)雜度。
• 2. RK算法的思想是這樣的：我們通過(guò)哈希算法對(duì)主串中的n-m+1個(gè)子串求哈希值甘桑，然后逐個(gè)與模式串的哈希值比較拍皮，如果相同就證明匹配成功了。（如果出現(xiàn)哈希沖突跑杭，可以將哈希值相同的兩個(gè)串铆帽，在進(jìn)行一次逐個(gè)字符的比較）
• 3. 整個(gè)RK算法可以分為兩部分：計(jì)算子串的哈希值、模式串的哈希值與子串哈希值進(jìn)行比較德谅。我們可以通過(guò)設(shè)計(jì)巧妙的哈希算法爹橱，使得掃描一次主串就可以得到所有子串的哈希值，這部分的時(shí)間復(fù)雜度為O(n)女阀；哈希值之間的比較的時(shí)間復(fù)雜度是O(1)宅荤，需要比較n-m+1次，所以這部分的時(shí)間復(fù)雜度也是O(n)浸策，所以整體RK算法的時(shí)間復(fù)雜度是O(n)冯键。

三、BM算法

• 1. BM算法是一種非常高效的字符串匹配算法庸汗，其性能是著名的KMP算法的3~4倍惫确。

• 2. 前邊講的匹配算法都是像下圖一樣，將模式串一位一位的往前移動(dòng)蚯舱，與主串的子串進(jìn)行一次一次的對(duì)比進(jìn)行查找的改化，而BM算法就第二個(gè)圖一樣，為了提高查找效率枉昏，找出了移動(dòng)規(guī)律陈肛，按照規(guī)律跳著往后移動(dòng)，例如：發(fā)現(xiàn)c與d不匹配了兄裂，就將模式串往后移動(dòng)三位句旱。

     
     
     模式串一位一位往后移動(dòng)
     
     
     BM找到了移動(dòng)規(guī)律，可以移動(dòng)多位

• 3. BM算法發(fā)現(xiàn)移動(dòng)規(guī)律有兩個(gè)：壞字符規(guī)則和好后綴規(guī)則
• 4. 壞字符規(guī)則
  • (1). 我們從模式串的末尾往前倒著匹配晰奖，當(dāng)我們發(fā)現(xiàn)某個(gè)字符沒法匹配時(shí)谈撒，我們就把這個(gè)字符叫做壞字符。
    
    壞字符.png
  • (2). 如果壞字符在模式串中存在匾南，那么我們就把懷字符對(duì)應(yīng)的模式串中的這個(gè)字符的下標(biāo)記做xi啃匿，如果懷字符在模式串中不存在，我們就把xi記作-1；我們把懷字符對(duì)應(yīng)在模式串中的字符的下標(biāo)記做si溯乒；規(guī)律就是：模式串往后移動(dòng)的位置就等于si-xi夹厌。如下圖所示：
    
    壞字符規(guī)則移動(dòng)位數(shù)
• 5. 好后綴規(guī)則

  • (1). 我們把主串中和模式串相匹配的字符，稱之為好后綴橙数，如下圖：

    
    
    好后綴
  • (2). 我們把好后綴bc記做{u}尊流，拿{u}在模式串中查找，如果找到了另一個(gè)跟{u}相匹配的子串{u*}灯帮，我們就將模式串滑動(dòng)到子串{u*}跟主串中{u}對(duì)齊的位置崖技，如下圖:
    
    找到與好后綴相同的子串，則滑動(dòng)對(duì)齊
  • (3). 如果在模式串中找不到另一個(gè)與{u}相匹配的子串钟哥，我們還得考察好后綴的后綴子串迎献，是否存在跟模式串的前綴子串相匹配。如果好后綴的后綴子串跟模式串的前綴子串相匹配腻贰，則將模式串滑動(dòng)到對(duì)齊的位置吁恍，如下圖：
    
    滑動(dòng)模式串到圖中位置
  • (4). 如果好后綴的后綴子串與模式串的前綴子串不匹配，則直接將模式串滑動(dòng)到主串的好后綴{u}的后面播演，如下圖：
    
    {u}代表好后綴
• 6. 當(dāng)模式串和主串中的某個(gè)字符不匹配時(shí)冀瓦，我們?cè)撊绾芜x擇使用壞字符規(guī)則還是好后綴規(guī)則呢？我們可以分別計(jì)算壞字符規(guī)則和好后綴規(guī)則往后移動(dòng)的位數(shù)写烤，然后取兩個(gè)數(shù)最大的翼闽，作為模式串往后移動(dòng)的位數(shù)。

第二十四章 Trie樹

一洲炊、什么是Trie樹

• 1. Trie樹感局，也叫字典樹，顧名思義暂衡，是一種樹形結(jié)構(gòu)询微，專門用來(lái)處理字符串匹配，經(jīng)常用來(lái)解決在一組字符串集合中快速查找某個(gè)字符串的問題狂巢。

• 2. Trie樹的本質(zhì)就是撑毛，利用字符串之間的公共前綴，將重復(fù)的前綴組合在一起唧领，就像下圖一樣：

     
     
     Trie樹

• 3. 利用how藻雌、hi、her疹吃、hello、so西雀、see等字符串構(gòu)造一顆Trie樹萨驶，過(guò)程如下圖所示：

     
     
     構(gòu)造一顆Tire樹

二、如何實(shí)現(xiàn)一顆Trie樹艇肴？

• 1. Trie樹主要有兩個(gè)操作：將字符串集合構(gòu)造成Trie樹腔呜、在Trie樹中查找一個(gè)字符串

• 2. Trie樹是一個(gè)多叉樹叁温，可以通過(guò)下標(biāo)和字符一一對(duì)應(yīng)的數(shù)組，來(lái)存儲(chǔ)子節(jié)點(diǎn)的指針核畴，如下圖所示：

     
     
     Trie樹的存儲(chǔ)
• 3. 一個(gè)Trie樹的結(jié)點(diǎn)膝但，用代碼可以這么寫：

class TrieNode{
    var data: Character?         //存放一個(gè)字符，例如：“h”
    var childArray: [TrieNode]?  //存放子節(jié)點(diǎn)指針的數(shù)組谤草，例如：存放以h開頭的字符的子節(jié)點(diǎn)的指針
}

• 4. 想在一組字符串中頻繁的查找一個(gè)字符串跟束，使用Trie樹解決就會(huì)非常高效，過(guò)程分為構(gòu)建Tire樹和查找該字符串丑孩。構(gòu)建Trie樹的過(guò)程需要掃描所有字符串冀宴，時(shí)間復(fù)雜度是O(n)，n代表所有字符串的長(zhǎng)度之和温学，一旦構(gòu)建Trie樹成功略贮，后續(xù)查詢就會(huì)非常高效，如果要查詢的字符串長(zhǎng)度為k仗岖，那么我們只需要對(duì)比大約k個(gè)節(jié)點(diǎn)逃延，就可以完成操作，時(shí)間復(fù)雜度為O(k)轧拄，k表示要查找的字符串的長(zhǎng)度揽祥。
• 5. Trie樹比較消耗內(nèi)存，是一種空間換時(shí)間的思路紧帕，用數(shù)組存放子節(jié)點(diǎn)的指針盔然，我們知道存放一個(gè)字符需要1個(gè)字節(jié)，而存放26個(gè)字母的指針是嗜，需要26*8=208個(gè)字節(jié)愈案，額外占用了208個(gè)字節(jié)，這還只是26個(gè)字母的情況鹅搪。我們可以將數(shù)組換成有序數(shù)組站绪、跳表、散列表丽柿、紅黑樹等數(shù)據(jù)結(jié)構(gòu)恢准，來(lái)節(jié)省內(nèi)存的消耗。

三甫题、Trie樹與散列表馁筐、紅黑樹的比較

• 1. 如果想要在一組字符串中精確查找某個(gè)字符串，一般建議使用散列表或者紅黑樹坠非。
• 2. Trie樹的優(yōu)勢(shì)不在于動(dòng)態(tài)集合數(shù)據(jù)的查找敏沉，而在于查找前綴匹配的字符串，例如：搜索引擎中的關(guān)鍵詞提示功能、輸入法自動(dòng)補(bǔ)全功能盟迟、IDE代碼編輯器自動(dòng)補(bǔ)全功能等秋泳。

第二十五章 AC自動(dòng)機(jī)

一、什么是 AC自動(dòng)機(jī)攒菠？

二迫皱、如何構(gòu)建AC自動(dòng)機(jī)?

三、如何在AC自動(dòng)機(jī)上匹配主串辖众？