联训总结 DAY 4

Manacher 算法

1.基础

Manacher算法是用来计算回文子串的。
以下内容转载自Segmentfault。

A. 问题定义

最长回文子串问题：给定一个字符串，求它的最长回文子串长度。
如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例：

12321 a aba abba aaaa tattarrattat（牛津英语词典中最长的回文单词）

B.Brute-force 解法

对于最长回文子串问题，最简单粗暴的办法是：找到字符串的所有子串，遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定，因此对于一个长度为n的字符串，共有n^2个子串。这些子串的平均长度大约是n/2，因此这个解法的时间复杂度是O(n^3)。

C.改进的方法

显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢？答案是肯定的。我们知道整个字符串中的所有字符，以及字符间的空隙，都可能是某个回文子串的对称轴位置。可以遍历这些位置，在每个位置上同时向左和向右扩展，直到左右两边的字符不同，或者达到边界。对于一个长度为n的字符串，这样的位置一共有n+n-1=2n-1个，在每个位置上平均大约要进行n/4次字符比较，于是此算法的时间复杂度是O(n^2)。

D.Manacher 算法

对于一个比较长的字符串，O(n^2)的时间复杂度是难以接受的。Can we do better?
先来看看解法2存在的缺陷。
1) 由于回文串长度的奇偶性造成了不同性质的对称轴位置，解法2要对两种情况分别处理；
2) 很多子串被重复多次访问，造成较差的时间效率。
缺陷2）可以通过这个直观的小串体现：

char: a b a b a
i ---: 0 1 2 3 4

当i==1，和i==2时，左边的子串aba分别被遍历了一次。
如果我们能改善解法2的不足，就很有希望能提高算法的效率。Manacher正是针对这些问题改进算法。

(1).解决长度奇偶性带来的对称轴位置问题

Manacher算法首先对字符串做一个预处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例：

aba ———> #a#b#a#
abba ———> #a#b#b#a#

插入的是同样的符号，且符号不存在于原串，因此子串的回文性不受影响，原来是回文的串，插完之后还是回文的，原来不是回文的，依然不会是回文。

(2).解决重复访问的问题

我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher定义了一个回文半径数组RL，用RL[i]表示以第i个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理，因此这里定义RL[i]为第i个字符为对称轴的回文串的最右一个字符与字符i的距离。对于上面插入分隔符之后的两个串，可以得到RL数组：

char: # a # b # a #
RL-- : 1 2 1 4 1 2 1
RL-1-: 0 1 0 3 0 1 0
i ----: 0 1 2 3 4 5 6

char: # a # b # b # a #
RL --: 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i ----: 0 1 2 3 4 5 6 7 8

上面我们还求了一下RL[i]-1。通过观察可以发现，RL[i]-1的值，正是在原本那个没有插入过分隔符的串中，以位置i为对称轴的最长回文串的长度。那么只要我们求出了RL数组，就能得到最长回文子串的长度。

于是问题变成了，怎样高效地求的RL数组。基本思路是利用回文串的对称性，扩展回文串。

我们再引入一个辅助变量MaxRight，表示当前访问到的所有回文子串，所能触及的最右一个字符的位置。另外还要记录下MaxRight对应的回文串的对称轴所在的位置，记为pos，它们的位置关系如下。

我们从左往右地访问字符串来求RL，假设当前访问到的位置为i，即要求RL[i]，在对应上图，i必然是在po右边的(obviously)。但我们更关注的是，i是在MaxRight的左边还是右边。我们分情况来讨论。

1）当i在MaxRight的左边

情况1）可以用下图来刻画：

我们知道，图中两个红色块之间（包括红色块）的串是回文的；并且以i为对称轴的回文串，是与红色块间的回文串有所重叠的。我们找到i关于pos的对称位置j，这个j对应的RL[j]我们是已经算过的。根据回文串的对称性，以i为对称轴的回文串和以j为对称轴的回文串，有一部分是相同的。这里又有两种细分的情况。

a）以j为对称轴的回文串比较短，短到像下图这样

这时我们知道RL[i]至少不会小于RL[j]，并且已经知道了部分的以i为中心的回文串，于是可以令RL[i]=RL[j]。但是以i为对称轴的回文串可能实际上更长，因此我们试着以i为对称轴，继续往左右两边扩展，直到左右两边字符不同，或者到达边界。

b）以j为对称轴的回文串很长，这么长：

这时，我们只能确定，两条蓝线之间的部分（即不超过MaxRight的部分）是回文的，于是从这个长度开始，尝试以i为中心向左右两边扩展，直到左右两边字符不同，或者到达边界。

不论以上哪种情况，之后都要尝试更新MaxRight和pos，因为有可能得到更大的MaxRight。

具体操作如下：

step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i为中心扩展回文串，直到左右两边字符不同，或者到达边界
step 3: 更新MaxRight和pos

2）当i在MaxRight的右边

遇到这种情况，说明以i为对称轴的回文串还没有任何一个部分被访问过，于是只能从i的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止。然后更新MaxRight和pos。

(3) 算法实现

void manacher(){
    int mx=0,id;
    for(int i=1;i<=n;i++){
        if(mx>=i){
            p[i]=min(mx-i,p[2*id-i]);
        }
        else{
            p[i]=1;
        }
        while(ch[i+p[i]+1]==ch[i-p[i]-1]){
            p[i]++;
        }
        if(p[i]+i>mx){
            mx=p[i]+i,id=i;
        }
        sum[0]++;
        sum[p[i]+1]--;
    }
}

(4) 复杂度分析

空间复杂度：插入分隔符形成新串，占用了线性的空间大小；RL数组也占用线性大小的空间，因此空间复杂度是线性的。
时间复杂度：尽管代码里面有两层循环，通过amortized analysis我们可以得出，Manacher的时间复杂度是线性的。由于内层的循环只对尚未匹配的部分进行，因此对于每一个字符而言，只会进行一次，因此时间复杂度是O(n)。

2.例题

A.Bzoj 2565 最长双回文串

题意

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

解析

不会。

参见CQzhangyu的博客

B.Bzoj 2084 Antisymmetry

题意

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。
现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

解析

不会。

参见hzwer的博客

后缀数组

思想来自一篇论文：后缀自动机——处理字符串的有力工具
内容部分来自老师的PPT。

后缀数组(suffix array)是一个一维数组，他保存0…n-1的某个排列sa[0],sa1….sa[n-1]，并且保证Suffix(sa[i])大于Suffix(sa[i+1]),0<=i

名次数组：名次数组rank[i]表示的是Suffix(i)在所有后缀中从小到大的排名。

可以看出后缀数组与名次数组是互逆运算。

举例子：AABAAAB

后缀--------SA-------RANK
AAAB------3---------2
AAB--------4---------4
AABAAAB--0---------6
AB----------5---------0
ABAAAB----1---------1
B------------6---------3
BAAAB------2---------5

如何求后缀数组？
直接暴力排序时间复杂度会达到O(N^2)甚至O(N^3)。
求解后缀数组有两种常规方法。
第一种是倍增算法，时间复杂度O(NlogN)。
第二种是DC3算法，时间复杂度O(N)，但是常数巨大。
实际二者效率差别并不明显，而DC3算法比较麻烦。
所以一般在算法竞赛中，倍增算法求后缀数组比较常用。

如果以上两者全都不会写，考试的时候可以用O(NlogN^2)的字符串hash+二分来代替后缀数组。

字符串hash

在字符串相关问题中我们可能会频繁的遇到要求判断两个字符串是否相同的操作。
一个一个字符比较显然太慢，那么我们可以用哈希算法来替代。
对于一个长度为N的字符串，我们可以定义他的哈希值为：
(S1*base^(N-1)+S2*base^(N-2)+…+S[N-1]*base^1+S[N]*1)%mod。
如果两个字符串hash值相同，我们可以姑且认为这两个字符串是相同的。
Hash值的计算方式：i从1到N，H[i]=(H[i-1]*base+S[i])%mod。
这样我们可以O(N)计算出长度为N的字符串的每一个前缀的hash值。
这样我们可以O(N)计算出长度为N的字符串的每一个子串的hash值。

基数排序
基数排序也叫桶排序，其主要思想为：

将每个元素视为若干个关键字，然后按优先级从低到高依次排序。
(例如我们可以将132视为拥有三个关键字的元素，其中1是第一关键字，3是第二关键字，2是第三关键字。
而我们就是从第三关键字开始排序，然后排第二关键字，最后按照第一关键字排序）。

而对于每次排序过程，我们依次把他们放入桶中再顺序拿出。

例如我们有数12,104,13,2,16,6
首先我们可以将这些数视为 012,104,013,002,016,006

我们开十个桶，分别代表0~9
先按照第三关键字（个位）排序，顺次将它们放入桶中，结果为
2号桶：012,002 3号桶：013 4号桶：104 6号桶：016,006

然后按照第二关键字(十位)排序，按照上一轮排好的顺序顺次入桶
0号桶：002,104,006 1号桶：012,013,016

最后按照第三关键字(百位)排序，结果为：
0号桶：002,006,012,013,016 1号桶：104

排序完毕，当M,X很小的时候，我们可以认为这个算法是线性的。

代码（极其恶心）

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l){
    return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m){
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) ws[i]=0;
    for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(i=1;i<m;i++) ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        for(i=0;i<m;i++) ws[i]=0;
        for(i=0;i<n;i++) ws[wv[i]]++;
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
return;
}

height数组
定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。

未完待续