用途 给一个首尾相连的字符串，找一个位置，从这个位置往后形成一个字符串，使字符串的字典序最小 算法 定义三个指针\(i=0\),\(j=1\),\(k=0\)，\(i\)和\(j\)是当前判断的位置，\(k\)是相同的串的长度，表示\(str[i...i+k]\)和\(str[j...j+k]\)相同。 当\(str[i+k]==str[j+k]\)时，显然，\(k++\)。 当\(str[i+k] > str[j+k]\)时，发现\(i+k\)位置的字典序要比\(j+k\)位置的字典序大，显然，\(str[j...j+k]\)的比\(str[i...i+k]\)的更优，字典序更小，那\...

预备知识： 二叉搜索树（BST） 至于BST，随便看一下就可以， 我们知道二叉搜索树是O(logN)的，那我们为什么要用平衡树呢？ 之前我们了解到，BST的插入是小的往左子树走，大的往右子树走，如果凉心出题人给出的序列是有序的呢  这样我们就只能O(N)的操作，GG 旋转(rotate)： Splay的经典操作就是旋转 在Splay中，我们用旋转来保持平衡，也就是保持是log(N)的量级 旋转就是将节点向上旋转到父亲节点的位置，同时保持平衡 有zig，和zag两种情况（其实都一个样）                                   具体要怎么旋转呢  如图，X，Y，Z 是三...

前言：平衡树的前置知识吧 二叉搜索树的定义： 二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根节点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉搜索树；   如图（一颗长残了的BST）：  二叉搜索树的查询： 若根结点的关键字值等于查找的关键字，返回根节点的值。 否则，若小于根结点的关键字值，递归查左子树。  若大于根结点的关键字值，递归查右子树。 若子树为空，则查找不成功。   假如我们要查询60 从根节点50开始，50 < 60 往右子树里找，到65，65...

预备知识：线段树，DFS序 DFS序   DFS序，字面意思，就是DFS到的顺序 我们只需要在搜到节点的时候记录一下就可以了 比如这样可能是一个树的DFS序  那知道了DFS序又有什么用呢 我们可以发现一颗子树在DFS序上是连续的一段  那么它就有了一个区间的性质，每个节点对应一段区间，那么我们在进行一些操作像什么：将以某节点为根的子树节点都加上x时，就可以转化为在线段树内的区间加了   树链剖分   首先我们要清楚一些概念： 重儿子（节点）：子树结点数目最多的结点 轻儿子（节点）：除了重儿子以外的结点 重边：父亲结点和重儿子连成的边 轻边：父亲节点和轻儿子连成的边 重链：由多条重边连接而成的...

最近浅学了一下匈牙利算法，略有感触，发文记录一下 匈牙利算法是用在二分图匹配中的 所以要先知道二分图的几个概念 二分图： 有这么一个图  把一个图的顶点划分为两个不相交的集合 U 和 V ，且使得每一条边都分别连接 U 、V 中的顶点，如果存在这样的划分，则称此图为二分图。 简单说，就是可以把一个图分为两部分，同一部分里没有边相连 如图：  匹配： 二分图匹配就是边集中的任意两条边没有公共顶点  如图，图中的红边叫做匹配 最大匹配： 一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配  当然，最大匹配不一定只存在一种 完美匹配 如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就...