Post 45

后缀数组进阶

height数组

个人感觉，上面说的一大堆，都是为heightheight数组做铺垫的，heightheight数组才是后缀数组的精髓、

先说定义

$i$号后缀：从$i$开始的后缀

$lcp(x,y)$：字符串xx与字符串yy的最长公共前缀，在这里指xx号后缀与与yy号后缀的最长公共前缀

$height[i]$：$lcp(sa[i],sa[i−1])$，即排名为$i$的后缀与排名为$i−1$后缀的最长公共前缀

$H[i]$：$height[rak[i]]$，即ii号后缀与它前一名的后缀的最长公共前缀

性质：$H[i]⩾H[i−1]−1$

看以下证明之前

证明引自远航之曲大佬

能够线性计算height[]的值的关键在于h的性质，即h[i]>=h[i-1]-1，下面具体分析一下这个不等式的由来。

我们先把要证什么放在这：对于第i个后缀，设j=sa[rank[i] – 1]，也就是说j是i的按排名来的上一个字符串，按定义来i和j的最长公共前缀就是height[rank[i]]，我们现在就是想知道height[rank[i]]至少是多少，而我们要证明的就是至少是height[rank[i-1]]-1。

好啦，现在开始证吧。

首先我们不妨设第i-1个字符串（这里以及后面指的“第?个字符串”不是按字典序排名来的，是按照首字符在字符串中的位置来的）按字典序排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。

这时，依据height[]的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rank[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。

第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为height[rank[i-1]]就是0了呀，那么无论height[rank[i]]是多少都会有height[rank[i]]>=height[rank[i-1]]-1，也就是h[i]>=h[i-1]-1。

第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面，要么就产生矛盾了。同时，第k个字符串和第i-1个字符串的最长公共前缀是height[rank[i-1]]，那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rank[i-1]]-1。

到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的字典序排名更靠前的那些字符串，谁和第i个字符串的相似度最高（这里说的相似度是指最长公共前缀的长度）？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rank[i]-1]。也就是说sa[rank[i]]和sa[rank[i]-1]的最长公共前缀至少是height[rank[i-1]]-1，那么就有height[rank[i]]>=height[rank[i-1]]-1，也即h[i]>=h[i-1]-1

唯一有点不懂的就是为啥LCP一定是前面那个后缀而一定不是后面那个呢。。。

然后我又认真读了一遍，发现前提是字典序排名更靠前的那些这个条件。。。在做题的过程中加深理解吧。

不同子串个数

题目背景

因为NOI被虐傻了，蒟蒻的YJQ准备来学习一下字符串，于是它碰到了这样一道题：

题目描述

给你一个长为N的字符串，求不同的子串的个数

我们定义两个子串不同，当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样。

子串的定义：原字符串中连续的一段字符组成的字符串

输入输出格式

输入格式：

第一行一个整数N

接下来一行N个字符表示给出的字符串

输出格式：

一行一个整数，表示不一样的子串个数

输入输出样例

输入样例#1：

5
aabaa

输出样例#1：

11

输入样例#2：

3
aba

输出样例#2：

5

说明

请使用64位整数来进行输出

（具体来说，C++和C选手请使用long long 类型，pascal选手请使用Int64）

由于输入文件过大，请使用 高效的读入方法（具体的，c++和c选手请不要使用cin，pascal选手不需要管）

对于30%的数据，N\le 1000N≤1000

对于100%的数据，N\le 10^5N≤105

题解

考虑将子串按照所属后缀分类。

枚举每个后缀，通过上述求出的Height数组我们可以知道每个后缀$i$之前的那些后缀与它的最大公共子串，这一部分之前被统计过了，所以对于这个后缀的$n-sa_i+1$个子串，有$Height_{rki}$个是重复的，

减去累加答案即可。

Code：

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
int rk[maxn] , sa[maxn] , h[maxn] , pos[maxn] , c[maxn] , n , m, ct;
char s[maxn];

inline void Sort()
{
    for(int i = 1 ; i <= m ; ++i)	c[i] = 0;
    for(int i = 1 ; i <= ct ; ++i)	++ c[rk[i]];
    for(int i = 1 ; i <= m ; ++i) c[i] += c[i-1];
    for(int i = ct ; i >= 1 ; --i) sa[c[rk[pos[i]]]--] = pos[i];
}

inline void getLCP()
{
    int k = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(k) --k;
        int cr = sa[rk[i]-1];
        while(s[i+k] == s[cr+k]) ++k;
        h[rk[i]] = k;
    }
}

inline void SuffixSort()
{
    m = 10000 , ct = n;
    for(int i = 1 ; i <= n ; ++i) rk[i] = s[i] , pos[i] = i;
    Sort();
    for(int k = 1 ; k <= n ; k <<= 1)
    {
        ct = 0;
        for(int i = 1 ; i <= k ; ++i) pos[++ct] = n - k + i;
        for(int i = 1 ; i <= n ; ++i) if(sa[i] > k) pos[++ct] = sa[i] - k;
        Sort();
        std::swap(pos,rk);
        rk[sa[1]] = ct = 1;
        for(int i = 2 ; i <= n ; ++i)
            rk[sa[i]] = (pos[sa[i-1]] == pos[sa[i]] && pos[sa[i-1]+k] == pos[sa[i]+k]) ? ct : ++ct;
        m = ct;
        if(m == n) break;
    }
    getLCP();
}

int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    SuffixSort();
    long long ans = 0;
    for(int i = 1 ; i <= n ; ++i)
        ans += n + 1 - sa[i] - h[i];
    printf("%lld\n",ans);
}

---

顺便放一下SAM的一些笔记（非正式）

果按照普通的字典树来建造的话，是以下的图：

但是我们看着可以发现有很多很多点都是重复的，浪费了很多空间，而且我们看到每个点大部分只有一个儿子，我们就想到利用公共部分把空间压缩，即把某些重复的边删去，连接到别的子树，从而利用公共部分降低空间复杂度，同时我们还要保证新的做法的正确性，并且降低时间复杂度降到大概O(n)O(n)，为了解决这个问题，后缀自动机诞生了qwqqwq

下图是后缀自动机成型样子（没显示failfail指针）：

后缀自动机是这样的:在后缀自动机中,为了节省空间,某个点有可能成为多个结点的儿子,可以保证在后缀自动机中遍历出来的所有字符串不会重复,而且刚好是原串s的所有子串。

基本储存信息：

11、ch[N][26]ch[N][26]：基本的字典树；

22、fail[N]fail[N]：指向上一个与当前节点等价的点

33、len[N]len[N]：表示以当前点为终点的子串的长度

后缀自动机的性质：

11、从任意节点到任意节点结束的路径都是文本串T的子串。

22、后缀自动机是一个根为rootroot的有向无环图

33、任何一个从任意节点到达任意节点p的路径是从根节点到p节点最长路径的一个后缀

……

算法流程：（假设要插入的字符为cc）

1、定义一个变量p=lastp=last； //lastlast为上一次的节点；

2、定义一个变量np=++cntnp=++cnt //cntcnt为节点编号（也可以理解为时间戳吧，反正差不多就是一种顺序），npnp为新添加的节点

3、last=nplast=np；len[np]=len[p]+1len[np]=len[p]+1 //更新上次的节点以及新节点的长度

4、循环判断：当pp点没有到cc的转移的话，ch[p][c]=npch[p][c]=np；即把pp点添加到cc的转移为npnp，并且pp点跳failfail指针，当pp点有到cc的转移时停止循环

5、当此时pp点为00时，把npnp的failfail指针赋为11（因为根节点rootroot为11）

6、否则的话，意味着此时的pp点有到cc的转移，我们定义q=ch[p][c]q=ch[p][c]

7、当len[q]==len[p]+1len[q]==len[p]+1时，把fail[np]fail[np]赋为pp并退出即可（具体后面会详细讲）

8、否则的话，我们定义一个新节点nq=++cntnq=++cnt，复制节点qq的chch数组，failfail指针给nqnq，len[nq]=len[p]+1len[nq]=len[p]+1，并且把npnp，qq的failfail指针赋为nqnq。循环跳pp点的failfail指针，每次当ch[p][c]==qch[p][c]==q时，ch[p][c]ch[p][c]赋为nqnq

（看到这里时是会有点懵逼的，等会结合下文图解及分析一起看）

先贴这部分代码（方便以后使用）：

+ View Code

　　

---

强势图解开始！！！

首先，假设我们已经建立好了文本串TT的后缀自动机，现在要在后面插入字符xx，使自动机成为字符串TxTx的后缀自动机，那么我们先建立一个新节点npnp，并且找到上一个节点pp，循环判断如果pp没有xx儿子的话，那么就向npnp连一条xx的转移，pp点跳failfail指针，直到pp点到了虚拟节点00或者有向x的转移时，停止循环。如果pp点此时是因为有向x的转移而退出的循环，即p!=0。假设此时pp点向x的转移为qq节点，那么就会有以下两种情况：

1、len[q]=len[p]+1len[q]=len[p]+1

我们因为想要压缩空间，那么就必须要共用已有的节点，下面是这种情况的图：

那么我们先考虑从pp点连一条xx的转移到npnp，但是这样可行吗？我们可以看出如果这样连的话，qq点就没有办法到达了，也就是说p−>q−>npp−>q−>np这一字串将会被破坏，那么怎么办呢？我们考虑把qq当做是npnp（因为都是向xx的转移），也就是说，把qq也当做是TT的某个字串的结尾，把npnp的failfail指针指向qq，从而保证算法的正确性（即性质11）

说到这可能大家会有疑问，如果我们不走pp节点就到了qq节点，那就不能保证到qq节点的都是TxTx的后缀了。其实len[p]=len[q]+1len[p]=len[q]+1就已经保证了经过了qq就必定经过了pp，如果不经过pp，那就只能从rootroot节点直接来了，为什么呢，我们运用反证法（转自某大佬）：

假设原命题不成立,那么就有两种可能:（补充：现在文本串为TxTx，也就是说xx是终点）

一.当前的xx字符,之前没有出现过.这样的话,有xx字符的子串必然是后缀,与假设矛盾.

二.当前的xx字符,之前已经出现过.这样的话,有xx字符而不是后缀的子串必然与之前的某个代表字符xx的结点连接,而不是与当前的xx点连接,否则后缀自动机的性质33早就被破坏了,故也与假设矛盾。

那么结束后的图是这样的（红色虚边为failfail指针，实线黑边为chch数组）：

2、len[q]>lenp[p]+1len[q]>lenp[p]+1

这种情况就是下图：

也面临着qq点能不能当做npnp点的问题。但是这种情况与第一种情况的区别在于：第一种情况pp，qq中间不会夹杂其他的字符，而这种情况pp，qq中间是会有其他字符的，我们就不能保证到达qq节点的一定是TxTx的后缀了。

那么我们考虑能不能把这种情况能不能转化为第一种情况呢？答案是肯定的，我们考虑新建一个节点nqnq，使得len[nq]=len[p]+1len[nq]=len[p]+1，这样的话我们就转化为了第一种问题，那么我们把节点qq所有东西复制给新节点nqnq的话，就让nqnq充当第一种问题中的qq，那么我们把qq，npnp的failfail指针赋值为nqnq，nqnq的failfail指针为pp，同时还必须记住让pp节点跳failfail指针，把所有连向qq节点的边都连向nqnq（因为nqnq节点代替了qq节点）

操作完成后就是下图：

---

图解acabb的后缀自动机过程，建议和代码一起理解！

（没有动图。。。动图太快了不好理解其实是本人不会）

1、插入aa字符：

因为pp一开始等于11（根节点），而所以根节点没有向aa的转移，因此向22连一条向aa的转移，然后跳failfail指针，然而fail[1]=0fail[1]=0，也就是指向了虚拟节点，所以fail[2]=1fail[2]=1（指向根节点）

2、插入cc字符：

建立新的节点33，pp节点为上一个节点22，pp没有向cc的转移，因此添加一个向cc的转移指向33，pp点跳failfail指针到了11,11节点也没有向cc的转移，也添加一个向cc的转移到33，跳failfail指针到00（虚拟节点），所以npnp节点的failfail指针指向11（根节点）

3、（重点）插入aa字符

这种情况就是len[q]=len[p]+1len[q]=len[p]+1的情况了，首先pp为33节点，然而现在pp节点没有向aa的转移，于是向npnp节点连一条aa的转移

并且pp点跳failfail指针到11节点，如下图：

而这时候我们发现pp节点有aa的转移指向22号节点， 并且满足上面所述的第一种情况即len[q]=len[p]+1len[q]=len[p]+1，所以直接把qq节点当做npnp节点

把fail[np]fail[np]赋值为qq，即下图：

4、插入bb字符

pp节点没有bb的转移，于是pp点向npnp连一条bb的转移

pp点跳failfail指针：

我们发现pp点没有bb的转移，于是pp点向npnp连一条bb的转移

pp点跳failfail指针：

最后pp点到了虚拟指针，所以将fail[np]fail[np]赋值为根节点11，完成后如下图：

5、（重点）插入bb字符：

这种情况就是第二种情况:len[q]>len[p]+1len[q]>len[p]+1

首先我们发现pp节点没有bb的转移，于是添加一个到bb的转移为npnp

pp跳failfail指针到rootroot：

我们发现pp点有bb的转移到qq节点，并且满足情况22（len[q]>len[p]+1len[q]>len[p]+1），复制qq点的信息到nqnq点（因为它要代替qq节点），即fail[nq]=fail[q]fail[nq]=fail[q]，并且nqnq也像qq一样连一条bb的转移到npnp，同时把qq，npnp的failfail指针赋值为nqnq

最后我们还要按照下图一样，pp点跳failfail指针把所有连向qq的转移都连向nqnq（nqnq代替了qq），如下图：

最终acabbacabb的后缀自动机就完成啦！

把failfail指针去掉就是下图：

---

后缀自动机的应用（借鉴了某大佬）：

1、检查字符串pp是不是文本串TT的子串

给定一个文本串TT，求字符串pp是不是TT的子串

首先，我们对文本串TT建立后缀自动机，然后在自动机上直接按照pp的每个字符来转移，如果转移失败的话，说明pp不是TT的子串，这些都是因为后缀自动机满足性质11。

2、不同的子串

给你一个文本串，求一共有多少子串

后缀自动机性质22，因为后缀自动机是一个有向无环图，所以我们可以考虑在上面简单的dpdp，根据性质22，任何子串都会是后缀自动机上的一段路径（包括长度为00的路径），所以我们令f[i]f[i]为ii节点不同路径的条数，即从ii节点开始有多少不同子串，状态转移方程就是：f[u]=∑v:(u,v)∈Ef[v]+1f[u]=∑v:(u,v)∈Ef[v]+1

那么我们最后的答案的话就是f[1]−1f[1]−1因为要去掉根节点长度为00的串

如果要考虑按字典序输出的话，那么就用一个手写栈来写，每次走字典序小的边，走到一个点就输出当前的栈内元素，递归后要回溯！

3、字典序第kk大的子串

其实这个问题是基于上面这个问题的，我们既然已经求出了每个点不同路径的条数，那么我们就可以选择性的走k小路径

4、字典序最小循环移位

给定一个文本串TT，每次操作可以把最左边的字符移到最右边，请求出字典序最小的循环移位

这个问题的话其实做多了就知道了，我们以T+TT+T来建立后缀自动机，这样的话后缀自动机就会包含每个循环移位的路径，那么我们直接贪心来找字典序最小就行了

【模板】循环移位

5、求两串中的最长公共子串

给定两个字符串为TT和SS，求出它们的最长公共子串

对于这个问题，我们对字符串TT建立后缀自动机，对于SS的每个前缀，在自动机里转移状态，定义一个ll变量，一个pospos变量，分别表示现在匹配的长度，以及现在的位置。我们每匹配成功一次，ll自增一，直到没有状态转移的时候，我们就跳failfail指针，而此时ll就要赋值为len[pos]len[pos]，直到pospos指向虚拟节点（也就是失配，此时l=0l=0）或匹配完成，而答案就是ll的最大值

6、出现次数

对于一个给定的文本串 $T$，有多组询问，每组询问给一个模式串 pp，回答模式串 pp 在字符串 $T$ 中作为子串出现了多少次

我们为文本串TT建立后缀自动机，为每个节点定义一个变量sizesize，初始化为11，根节点与复制节点nq除外，那么我们对每个节点做如下操作：size[fail[pos]]+=size[pos]size[fail[pos]]+=size[pos]，含义是当节点pospos出现了size[pos]size[pos]次，那么以它为后缀的点也会出现这么多次。最后查询size[t]size[t]，tt就是模式串的状态，查询不到则为00

---

练习：

P3804【模板】后缀自动机

没什么好说的，就是模板

P3649[APIO2014]回文串

要用用上面的知识点，灵活运用吧qwqqwq，相信你会举一反三的

---

今天晚上又读了读lrj的紫书上关于SAM（其实是广义自动机）的介绍，感觉对SAM又了解了一点，对于它的各种神器性质和思想也理解的更多了。

上面那些杂乱的笔记是我偶然翻到一个blog关于一点一点模拟的，可以增加感性理解，不过对于这个高级算法更重要的还是理解其各种性质才能学会构造（吧）

明天一天一定要学会SAM！！！

---

看了道很简单的线段树维护最大字段和，连代码都懒得写了。。

简述方法：

分情况讨论，对于当前区间，如果我们想通过左右区间快速合并当前区间信息，需要维护左端开始的的最大子区间，右边开始的，以及当前答案（即左右最大或左边的右最大和右边的左最大合并来更新答案）

参考Code：

inline void update(int p)
{
    s(p)=s(p<<1)+s(p<<1|1);//该区间和为左区间和+右区间和
    lm(p)=max(s(p<<1)+lm(p<<1|1),lm(p<<1));//左区间最大子段和 或 左区间和+右区间左子段和
    rm(p)=max(s(p<<1|1)+rm(p<<1),rm(p<<1|1));//右区间最大子段和 或 右区间和+左区间右子段和
    m(p)=max(max(m(p<<1),m(p<<1|1)),rm(p<<1)+lm(p<<1|1));//左区间最大子段和 或 右区间最大子段和 或 左区间右子段和+右区间左子段和
}

还说今天之所以什么都没干成的原因是这个笔记本又卡死了啊啊啊啊。

幸好找到了问题所在，把win10那臭名远扬的自动更新关掉了。