Posts

KMP已经介绍过了，这次主要介绍的是Manacher

最长回文子串

Manacher算法要解决的问题就是求最长回文子串，用到的思维和扩展KMP实在是像，不过理解起来比扩展KMP简单。

先定义数组v，v[i]表示以第i个字符为中心，到回文串一端的距离，我们以字符串"acabacab"为例，如下表（index是下标）

i是当前要计算的指针，m是上次计算的指针，e是下一个要比较的位置的指针

然后++i，注意这时候，由于以字符b两边是对称的，所以在求v[4]的值的时候，可以先查v[2]的值，是1，所以v[4]也是1

再继续++i，同样的，在求v[5]的值的时候，可以先查v[1]的值，是2，但是，这个长度达到了e指针的位置，即i+2>=e，这时候就更新指针m，并扩展e的位置，即比较str[7]与str[3]，找到以下标5为中心的回文串边界。

讲完了treap和splaytree，接下来讲把这两的思想混合在一起的 FHQ Treap，据说作者是范浩强。

splay其实还有两个操作split和merge没有介绍，我打算把这两放在这里一并介绍

Split和Merge

Split就是把树按某个条件划分成两棵子树，如果是查找树，就按某个值划分为小于它的以及大于等于它的（等于号取哪边怎么好写怎么来就是），如果是序列维护，那就按照rank来划分。而merge操作则正好相反，把两棵子树合并成为一棵。所以，如果我们需要对某个区间做操作，那么我们就把那个区间Split出来，操作好了后（打懒惰标记，或取出结果）再Merge回去就行了，与splay操作的思路是差不多的。不过为了在split再merge后能间接对树的平衡性优化，我们不能简单地merge，要套用Treap的随机数法，我们先来看怎么split。

先定义好接口void split(int tp, int k, int &x, int &y)，x是返回的左子树，y是返回的右子树，接着我们需要递归split，如果划分点在左子树，那么y一定是根，反之划分点在右子树，那么x一定是根。确定了其中一个，在递归调用的时候，假如y确定了，于是还没确定的，就是x以及根节点的左子树的指向，所以把这两传参就行了，时间复杂度 $O(logn)$ ，具体代码如下：

// 维护序列的实现
void split(int tp, int k, int &x, int &y)
{
    if (!tp) { x = y = 0; return; }
    pushdown(tp);
    if (k <= nodes[ch(tp, 0)].sz)
    {
        y = tp;
        split(ch(tp, 0), k, x, ch(tp, 0));
        update(y);
    }
    else
    {
        x = tp;
        split(ch(tp, 1), k - nodes[ch(tp, 0)].sz - 1, ch(tp, 1), y);
        update(x);
    }
}

平衡树除了用来对存在偏序关系的数据进行维护，还能用于对序列维护，相当于一个数组。阅读本文你需要先看完上一篇关于treap的文章。

序列维护

在之前的文章，我们介绍过使用树状数组，以及线段树来维护一个序列，可以做区间操作及区间求和，但它们都存在一个缺点，不能动态插入数据。那我们怎么样才能通过平衡树来维护序列呢，之前我们有一个size字段能快速找第k大（或树的中序遍历第k个元素），而旋转操作并不会改变元素之间的相对顺序，那么我们就通过它直接插入到第k个元素的前面，这样我们插入的时候就不再通过要插入的值本身的大小关系，而需要多加一个参数k决定插入的位置。当平衡树用于维护序列的时候，就不用考虑元素相等的问题了。这样我们把元素相等处理的代码删除并修改基本操作的代码就能得到第一个能维护序列的基本模板，以下模板使用Treap修改得来。

这里之所以把这两个放在一起讲，是因为它们实在是相似度很高（至少在竞赛领域），都需要求kth和指定元素的rank（Treap的话可有可无，但通常会需要）。不过如果你没有写过树，强烈建议你自己通过理解来写一遍。

BST

首先，Treap和SBT都属于BST的一种，BST就是二叉搜索树，它满足的特点是：

• 二叉树
• 没有两个节点的值相等
• 任意子树的根节点的值都比左子树所有节点的值要大
• 任意子树的根节点的值都比右子树所有节点的值要小
• 任意子树均为二叉搜索树

如果我们实在需要支持多个相同值放在树里面，那么有两种情况，如果那些相同值是确实完全没有区别（例如int），那么只需要在每个节点多加一个字段记录这个值出现的次数就可以了，但如果这些值只有偏序关系，可能不是严格相等，存在其它非比较字段，那么我们就再在每个节点增加一个next域做成一个链表即可。

很多人在初始接触线段树的时候，一看到别人写一大堆代码就直接弃坑了，其实不要被它的外表所欺骗，线段树其实是相当好写的树结构了，而且理解起来其实很简单。要学会这个，你不能光会抄模板就会区间修改和求个区间和，因为实际应用经常会使用它的变形，还是在于理解（理解后背板）。

数据结构

首先，回想一下heap的结构，它使用一个数组，同时使用下标本身来表达父子关系，这样的方式能节省大量指针所需要的内存空间，以下也使用这种表示方法来表示一棵线段树，也就是说，这里介绍的，属于狭义线段树。假设我们的数据是以下这样

构建线段树后结果如下

graph TD;
1,8:16-->1,4:8
1,8:16-->5,8:8
1,4:8-->1,2:1
1,4:8-->3,4:7
1,2:1-->1,1:1
1,2:1-->2,2:0
3,4:7-->3,3:5
3,4:7-->4,4:2
5,8:8-->5,6:7
5,8:8-->7,8:1
5,6:7-->5,5:3
5,6:7-->6,6:4
7,8:1-->7,7:0
7,8:1-->8,8:1

后缀数组其实概念很好理解，就是给出一个字符串，长度是n，对它所有的n个后缀编号从1到n进行排序，排序后，最小的那个后缀的编号假设是m1，那么sa[1] = m1，类似地，第二小的是m2的话，sa[2] = m2，sa这个数组就是我们所需要的后缀数组。根据这个，我们可以直接用sort算出sa，以下为最简单的实现

struct SA_simple
{
    vector<int> sa;
    int s_size;
    const char* p_s;
    int size() const
    {
        return s_size;
    }
    static bool cmp(const char* x, const char* y)
    {
        return strcmp(x, y) < 0;
    }
    void init(char * str)
    {
        int n = strlen(str);
        s_size = n;
        p_s = str - 1;

        sa.resize(n + 1);
        vector< const char* > rp;
        rp.resize(n + 1);

        for (int i = 1; i <= n; ++i)
        {
            rp[i] = p_s + i;
        }
        sort(rp.begin() + 1, rp.end(), cmp);
        for (int i = 1; i <= n; ++i)
        {
            sa[i] = rp[i] - p_s;
        }
    }
};

这个实现的时间复杂度 $O(n^2logn)$

要注意的一点是下标从1开始。有了这个，可以做点什么呢？例如给你一个串p，求出p在主串s中出现了多少次。那么在有了sa的情况下，因为sa是有序的，问题就变成了二分搜索，分别用lower_bound和upper_bound通过sa搜索p，两个相减便得出现次数。

树状数组，是一个用于在近似 $O(logn)$ 时间内动态修改以及查询前缀和的数据结构，以下我们先来看以下树关系表格

这里表达的是，16的子节点有8, 12, 14, 15

8的子节点有4, 6, 7

12的子节点有10, 11，即夹在12与它的同级节点8之间

我们把数值与它的二进制一起形象化画出下图

graph TD;
2,0010-->1,0001
4,0100-->3,0011
4,0100-->2,0010
6,0110-->5,0101
8,1000-->7,0111
8,1000-->6,0110
8,1000-->4,0100
10,1010-->9,1001
12,1100-->11,1011
12,1100-->10,1010
14,1110-->13,1101
16,10000-->8,1000
16,10000-->12,1100
16,10000-->14,1110
16,10000-->15,1111

这样构造的原理是运用到一个二进制运算技巧，假设一个节点x，那么它的父节点就是x + (x & -x)，其中，x & -x是去掉右起第一个1的左边的1，例如x如果是6，二进制是110，只保留最右边的1结果就是10了，所以6的父节点就是6+2=8，更多的可以参考这篇二进制技巧。

KMP之所以在竞赛中常见，并不是因为它用来匹配字符串，而是用它的next数组，为了介绍它，我们先讲讲最长公共前缀

最长公共前缀

我们拿字符串ababcab作为例子

这里所表达的是，例如取第3、4个字符”ab”，这个子串与前缀完全匹配，且它的长度是2，所以就记录2，而第3、4、5个字符”abc”与前缀不能完全匹配，就记作0，含义就这么简单，而且你会发现，计算b的时候，可以根据它所匹配的字符的偏移来，b如果是匹配的，就找到匹配的那个字符是数组中的第几个，它是第二个，所以填2进去。我们再来看更复杂的例子

最后那个字符不匹配的时候，1是怎么计算出来的呢，直接重新计算当然也可以，但就出现重复计算了。我们考虑一下匹配过程，在前面的字符a的时候，前后各一个指针，像这样

然后两个a匹配，arr[6] = pointer1 - arr 得到3，然后两指针一起移动

这时候，不匹配，那么前一个指针上一次指向的是arr[2]的位置，即图上*的地方，值是1，这个值如果是p，那就移动到arr[p]的地方，所以就移动到arr[1]的地方，本质上就是找到前一个匹配此后缀的位置，即

然后再尝试匹配，这次匹配上了，然后前一指针指向第二个元素，所以赋值2

在上一篇我们介绍了快排的各种优化，最后得到了一个超越VS的STL std::sort实现的版本，这回我们来讲讲怎么折磨gcc的std::sort。

GCC的实现

这个我直接给个github来源，链接里是gcc8分支的实现源码，我已经通过链接标记出第1896行，那里就是__unguarded_partition函数的实现，就是快排的划分函数，而在后面几个函数就是快排的本体了。为了避免它代码更新导致位置变化，我把相关代码复制过来。

在上一篇我们介绍了四种不同的划分算法，现在我们来针对Hoare partition scheme来讲解一些优化和注意的问题。

最坏时间复杂度的优化

在前一篇的示例代码里面，只是最简单地选择的最开头或最后面的元素作为划分，这对于乱序的数据还好，对于有序的数据这么做，时间复杂度就直接变成$O(n^2)$了，那么怎么解决？第一个要解决的反而不是划分元素的选择上，而是改成intro sort，记录递归深度或类似的办法，到达限制条件的时候改而使用堆排序，这属于混合排序，先让排序的最坏时间复杂度降下来是第一要务。所以可以改写出以下代码：