Aull Chen's Blog

字符串匹配 This article is a study note on Introduction to Algorithms. 定义 顾名思义，在一个目标串中寻找是否出现模板串的过程，为字符串匹配。 算法 预处理时间 匹配时间 朴素算法 000 O((n−m+1)m)Ο((n-m+1)m)O((n−m+1)m) Rabin-Karp Θ(m)\Theta(m)Θ(m) O((n−m+1)m)Ο((n-m+1)m)O((n−m+1)m) 有限自动机算法 $Ο(m \Sigma Knuth-Morris-Pratt Θ(m)\Theta(m)Θ(m) Θ(n)\Theta(n)Θ(n) 朴素字符串匹配算法 最简单直观的算法，又叫做BF(Brute Force)算法。两层循环，逐一比较目标串与模式串之间的每一个字符是否匹配。 伪代码 123456NAIVE-STRING-MATCHER(T,P) n = T.length m = P.length for s = O to n — m if P[1..m] == T[s+1.. s+m] print ...

最小生成树 在阅读下列内容之前，请了解 图 和 树 相关内容，并了解以下定义： 生成子图 生成树 定义 我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。 注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。 Kruskal 算法 Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。 前置知识 并查集、贪心、图的存储。 实现 伪代码：（不写正经代码是因为不想写并查集……真想看去找AI吧~） 1Input. The edges of the graph e, where each element in e is (u,v,w) denoting that there is an edge between u and v weighted w.2Output. The edges of the MST of the input graph.3Method. 4result←∅5sort e into nondecreasing order  ...

多源最短路 请确保自己已经了解图的相关内容。包括但不限于： 图，邻接表，邻接矩阵 路径，最短路，权，环 有向图，无向图 Dijkstra算法，Bellman-Ford算法 文中所有的证明都是不严谨的，详细数学证明可移步《算法导论》相关章节。 定义 顾名思义，求一张图上所有节点到其他可连通节点的最短路径。 最短路算法 Floyd Johnson Dijkstra Bellman–Ford 最短路类型 每对结点之间的最短路 每对结点之间的最短路 单源最短路 单源最短路 作用于 任意图 任意图 非负权图 任意图 能否检测负环？ 能 能 不能 能 时间复杂度 O(N3)O(N^3)O(N3) O(NMlog⁡M)O(NM\log M)O(NMlogM) O(Mlog⁡M)O(M\log M)O(MlogM) O(NM)O(NM)O(NM) 注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。 Floyd 算法 弗洛伊德算法可以用来求任意两个结点之间的最短路。 复杂度比较高，但是常数小，容易实现（只有三个 fo ...

单源最短路 请确保自己已经了解图的相关内容。包括但不限于： 图，邻接表，邻接矩阵 路径，最短路，权，环 有向图，无向图 定义 顾名思义，求单一起点到其他可连通节点的最短路径。有两种比较经典的算法： 最短路算法 Dijkstra Bellman–Ford 最短路类型 单源最短路 单源最短路 作用于 非负权图 任意图 能否检测负环？ 不能 能 时间复杂度 O(Mlog⁡M)O(M\log M)O(MlogM) O(NM)O(NM)O(NM) 注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。 Dijkstra 迪杰斯特拉算法是一个经典的求单源最短路的算法。其优点是容易理解，在数据量不大的情况下拥有较好的效率。缺点则是无法处理存在负权边的图。 过程 先介绍Dijkstra算法要用到的松弛操作（后面的Bellman–Ford算法也会用到松弛操作）。 对于边(u,v)，松弛操作对应下面的式子：dis(v)=min(dis(v), dis(u)+w(u,v))。 这么做的含义是显然的：我们尝试用S->u-> ...

578a9066b62d8523a8d89172458a1de0083f677eaaa2c8617876a64f0711673a478e7fa81a1002ea441188a72ce3e1db673e9c84a7356ecf5524c4fe7dbcd98e9f347382536defa58947b58245ca20dfae5260420b99c2c6fa953aecdc1b857ddc48e9f51264b44982b4a491ae2fb1b6c54c10ac903c819763208ebb6ac48b08ee7e0f7f7a5e114a14f7ddc504017d8b5c3be9f5da5c3a8baa6eca63d73ad276e0b9f5e06d79c91efe14925bf4c0510ed6b62c25f297fcde9a4ea5a55406192dbd7606582a52c453d2ffbb014c35e9b9cf51fb033d1c2d93abf2513feaa01503d8a5d96fab9d498352692ad2ee0e7394022ff7f7dfabcbe49 ...

多重背包 前言 多重背包问题，和完全背包问题相比，其实就是每个物品可以取的数目是限定的。 一、经典多重背包 有 n(n ≤ 100)种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i]，价值是 w[i]。现在需要选择一些物品放入背包，每种物品可以选择 x[i] 件，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。 1、状态设计 状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n，0 ≤ j ≤ m)； 令dp[i][j]表示状态(i, j)下该背包得到的最大价值，即前i种物品（每种物品可以选择x[i]件）恰好放入容量为j的背包所得到的最大总价值； 2、状态转移方程 dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)   (0≤k≤x[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ \ (0 \le k \le x[i]) dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)   (0≤ ...

动态规划 之 完全背包 前言 完全背包问题，相比 0/1背包问题，其实就是每个物品可以取无限次，就像“完全披萨”一样（无端联想） 一、完全背包𢖩莉 典例 有 n(n ≤ 100) 种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i]，价值是 w[i]。 现在需要选择一些物品放入背包，每种物品可以无限选择，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。 以上就是完全背包问题的完整描述，和 0/1 背包的区别单纯在于每种物品可以无限选取。 1、状态设计 状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n，0 ≤ j ≤ m)； 令 dp[i][j] 表示状态 (i, j) 下该背包得到的最大价值，即前i种物品（每种物品可以选择无限件）恰好放入容量为j的背包所得到的最大总价值； 2、状态转移方程 dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)  (0≤k≤jc[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ ...

动规入门：0/1背包 前言 0/1 背包问题，作为动态规划问题的经典问题，可以帮助捋顺思维。之所以叫0/1背包，是因为在这类问题中每种物品只有一个，每个物品只有放和不放两种选择，即对于一种物品，可以表示为0和1两种状态。因此0/1背包统计的是 恒定容量 储存数个 不同物品 的 最大价值。核心在于确认好初始状态、递推基数和递推增量（反正就是dp[i][j-?] + ?，理解万岁）。说白了主要难点还是在确认递推关系上。 一、经典0/1背包问题 有 n(n ≤ 100) 个物品和一个容量为 m(m ≤ 10000) 的背包。 第 i 个物品的容量是 c[i]，价值是 w[i]。现在需要选择一些物品放入背包，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。 1、状态设计 动态规划的最核心之一是确认好dp数组的含义。这决定了你接下来的递推关系和最终问题的返回值。（不知道为什么叫dp数组的自己去查动态规划的英文）每次当你找递推关系出现问题的时候，最好的方法就是回头看一下你确认的dp数组的含义。如果实在找不出，那就要考虑是否在这最开始就出现了问题。 在01背包问题中，我们一般情况下 ...

博客文章多了，某天突然发现，有一个tag点进去404，在本地运行hexo s却正常没有问题。 首先是老传统STFW，但是网络上的相关内容却都是解决tags总页面404的，我却是单独的tag页面丢失，没找到我想要的内容。用实力证明搜索引擎不可靠（笑）。刚好那段时间比较忙，就暂且把这事搁置了。（反正博客也没什么人看） 中间有一天突发奇想，把链接里相关tag的大写改为小写，发现可以访问了。没时间去解决（懒狗不想手动修改每一个tag），于是在Tags页面下写了条评论。 今天闲下来突然想起还有这事。搜索引擎一如既往稳定发挥。怎么办呢？不急，我还有一招——RTFM。找到hexo在Github上的仓库，在Issues里面寻找。果然找到了老前辈的馈赠——BUG反馈：大写开头的标签出现404 · Issue #818 · hexojs/hexo (github.com) 在里面逛了一圈发现是因为git中设置了大小写不敏感。 解决过程 在网上查找修改 git 设置不忽略大小写的方法。（顺便看到了很多因为这个引发的“事故”哈哈） 进入博客文件夹的 git 目录：.deploy_git，修改 .git 文件夹 ...

二分枚举 前言 二分查找的问题可以理解如下：在一个序列上，某个特定的标记将其分成左右两个部分。我们需要找到这个标记的位置在哪两个元素中间。当然，我们实际需要的显然不是这个标记，而是挨着标记的元素，因此二分查找一个需要特别注意的地方就是选取标记左边还是右边的元素返回。一个需要查找的序列可以抽象成下面的形状：(确实很抽象) □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□^□□□□□□□□□□□□□□□□□□□□□□□□□□□ □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□^ ^□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ 一、线性枚举 1、定义 线性枚举指的就是遍历某个顺序表（如一维数组）的所有元素，找到满足条件的那个元素并且返回，返回值可以是下标，也可以是元素本身。 由于是遍历的，穷举了所有情况，所以一定是可以找到解的，一些资料上也称之为 暴力算法 （Brute Force）。 2、时间复杂度 ...