Z算法核心 和KMP算法类似，Z算法大核心也是那一个数组，或者叫z函数。 首先我们定义一下什么叫z数组。 一句话说：在一个字符串里面，从当前符号匹配字符串开头，能匹配到的最大长度。 举个例子： s: abcabca z: 0004001 需要注意的是z[0]=0。为什么z[3]=4?可以把从i=3这个字符串抽出来，我们比较 s: abcabca i=3 abca 可以看到从i=3开始，这个和s前缀比较最大长度就是4。 如何得到z数组 首先我们来看暴力法怎么做： vect… More »
字符串匹配是一个很常见的问题，例如从一个长的字符串：saippuakauppias，我们要匹配模式字符串pp。可以用暴力破解法，复杂度是$O(nm)$n是长字符串的长度，m是模式字符串的长度。 于是几个聪明的人发明了KMP算法。 暴力破解法的一个很大的问题就是需要一个一个比对，如果比对错了，那么下次就从下一个还是一个一个比对。这样的坏处就是没有好好利用之前已经得到的信息。KMP算法就很好的解决了这个问题，可以利用之前的信息。 $\pi$（pi）表 KMP算法最重要的一个就是$\pi$表。 什么是$\pi$表？一句话概括：预处理模式串P中… More »
Trie是一个可以快速检索字典的一种数据结构。本篇文章我们以存储英语单词，存储a-z的26个英语字母。 class TrieNode { TrieNode* children[26]; bool leaf; }; 上面， children[]： 大小为26的数组存储指针。由于我们是可以通过 字母-'a'的方式得到每一个字母的数值，因此字母可以和数组下标对应上。 leaf：标志是否是一个单词的结尾 图片来源于https://www.geeksforgeeks.org/ Trie的基本操作 Trie最主要的操作有… More »
假设有一个长度为6数组： a=[0,0,0,0,0,0] 现在想在L-R之间添加3，那么就需要每一个数迭代的添加，但是这样就太慢了。这个时候差分数组的作用就体现出来了：只需要记录两个端点的情况，然后最后统一处理就可以了。 例如L=1，R=3，循环增加得到的结果是a=[0,3,3,3,0,0]。 我们可以记录一个差分数组d[1]=3, d[4]=-3。于是d=[0,3,0,0,-3,0]，在最后得到结果的时候就是： $a[i]=a[i-1]+d[i]$ 那么$a[0]=0,a[1]=a[0]+d[1]=3,a[2]=a[1]+d[2]=3…a[4]=a[3]+d[4]=3+(-3)=0$。 可以… More »
BIT是什么？全称Binary indexed tree，或者Fenwick tree。用在区间查询和更新里面。相对于前缀和数组的一个优势在于可以动态更新数据，复杂度是$O(logn)$ 核心公式： $tree[k]= sum_q(k− p(k)+ 1,k)$ $p(k)$代表可以被k整除的最大的2的幂数。$p(k)=k\&-k$。为什么？由于$k\&-k$得到的是k的最低有效位，实际上k的最低有效位就是刚好能被k整除的数。因此可以快速的算$p(k)$。 这个公式的规律就是如果是奇数那么这个范围就是只有自己。 核心实… More »
DFS，深度优先遍历，图的一种常用的遍历方式。核心思想是从每个节点，沿着子节点一直走，走到最深，因此叫做深度优先。 常见的方式是用递归的方法实现的，但是递归有一个问题需要注意递归的深度，因此在某些情况下需要用到迭代到方式。 DFS的本质是一个栈的形式。栈是一种后进先出的数据结构，也就是说会优先处理最近添加的数据。这个和DFS的处理方法不谋而合。因此我们可以用这个栈来模拟DFS过程。 为了防止重复访问节点，因此需要一个visit数组来去重。 迭代实现cpp代码如下： # 传入一个根节点 # 我们采用邻接表的方式表示一个图。邻接表就是给定一个节点，可以找到这个节点的全部邻居。 #include &… More »
题目来自于cses: # Company Queries II 解体思路： 这是关于树问题比较典型的问题求最小公共祖先。 首先想到的应该是把两个需要查询的节点首先拉到一层，之后一层一层的网上查找。 但是这样的时间复杂度是：$O(q \times (lgn + n)$。接近$O(N^2)$时间复杂度肯定是不行的。 现在的问题就是如何去优化一层一层查找这个过程。 其实也可以用倍增法。 在把两个节点拉到同一水平之后，贪心的思想，让节点同时尽可能往上面跳跃。但是不能让他们跳到相同的点，因为相同点其实就是根节点1了。因为所有数都是可以用二进制表示的，参考[[倍增法/index|index]]。 那么可以… More »
解释 倍增法的核心起源于每一个数字都可以使用二进制表示： 13 = 8+4+1=0b1000 + 0b0100 + 0b0001 那么我们先预处理这样的一个表，之后是不是就可以直接使用，快速得到结果呢？相比于一层层的获取的时间复杂度O(n)，倍增法的事件复杂度是O(lgn) 数据结构： up[i][j]表示在i点$2^j$跳达到后的点。 up[i][0]表示i点点直接parent 核心公式： mid = up[i][j-1] // 从i经过2^(j-1)跳到达mid up[i][j] = up[mid][j-1]… More »