Blog
I use blog to record something.
KMP
KMP基本思想 设主串（下文中称为A串）为：a b a a b a b 模式串（下文中称为B串）为：a b a b （两个串的第一个下标都为1） 首先，若按照朴素算法，当发现A串与B串失配的时候，就会枚举A的下一位重新开始匹配，...
康托展开
简述 康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。 原理 X=a...
哈希表
哈希表 其实就是把很多数对一个大质数取模，然后把模数相等的放到一个链表里面，最后查询就行了。有点像非常像前向星存图 构造 1.除余法 选一个适当的数b，然后用其对b取模的数作为哈希值，即H(x) = x mod b,如果b的约数越多，...
Hash
哈希 哈希的思想比较简单，其实就是把一个字符串看做一个高进制的数。 滚动哈希 子字符串匹配，复杂度O(n+m)。 -流程 我盟选取两个合适的互质的常数b和h(b<h)，假设字符串为C=$C_1C_2C_3..C_n$那么我们定义...
双向bfs
其实很简单，就是两边一起搜。板子如下luogu UVA439 # include <iostream> # include <algorithm> # include <queue> # inclu...
二分陷阱
范围缩小时，对mid值的改变 前提while(l < r) 1.缩小范围时，r = mid,l = mid+1 ,则，mid = (l+r)»1; 2.缩小范围时，l = mid,r = mid-1,则，mid = (l+r+1...