史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法

时间限制:10000ms
单点时限:2000ms
内存限制:512MB

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中出现了多少不同的旋律？

输入
共一行，包含一个由小写字母构成的字符串。字符串长度不超过 1e6。

输出
一行一个整数，表示答案。

样例输入
aab

样例输出
5

ps: 这里多说一句整个SAM的构造大体发生什么事情. 以便读者对SAM的构造全貌有个清晰的认识. 因为我们【1】中
也提到了. SAM是要识别所有子串的机器. 而子串不就是前缀的后缀么(或者后缀的前缀, 到底哪种观点来看待子串要
根据具体情形)? 所以SAM的构造过程是每次新读入一个字符S[i+1], 则新产生的前缀是S[1,..,i+1], 而它的所有
后缀是S[1,..,i+1],S[2,..,i+1],...,S[i,i+1],S[i+1] 这i+1个后缀. 我们每次升级改造SAM其实就是
要保证升级改造之后, 这i+1个后缀在SAM中能被识别. 或者说这i+1个后缀中任何一个都能找到一个节点作为归属.
如果这i+1个后缀中有后缀在改造前的SAM中找不到节点作为归属的话，则就要新建节点来作为归属——即SAM产生了新
的状态. 注意, 这i+1个后缀中不是每个后缀都要新建节点的. 例如 abba, 读入S[4]=a, 新增的4个后缀是
abba、bba、ba、a, 对于最后的那个后缀"a"而言, 就不需要新建节点. 因为既有的SAM中已经有节点可以作为它
的归属了. 但是我们可以断言每次升级改造至少会诞生一个新的节点, 因为S[1,...,i+1]比当前任何前缀都要长.
它不可能属于任何一个既有节点.

//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
typedef long long ll;
const int maxn = 1e6+5, SZ = 26;
int n; // n 是sam节点个数, sam的节点标号从0开始(sam[0]是sam的起点状态)
char s[maxn];

struct SamNode
{
	int trans[SZ], slink;
	int shortest, longest;
}sam[maxn<<1];

int newnode(int shortest, int longest, int *trans, int slink)
{
	sam[n].shortest = shortest;
	sam[n].longest = longest;
	sam[n].slink = slink;
	trans?memcpy(sam[n].trans, trans, SZ*sizeof(int)):memset(sam[n].trans, -1, SZ*sizeof(int));
	return n++;
}

int insert(char ch, int u)
{
	int c = ch - 'a';
	int z = newnode(-1, sam[u].longest+1, 0, -1);
	int v = u;
	while(~v && !~sam[v].trans[c])
	{
		sam[v].trans[c] = z;
		v = sam[v].slink;
	}
	if (!~v)
	{
		sam[z].shortest = 1;
		sam[z].slink = 0;
		return z;
	} // 参见附录图1
	int x = sam[v].trans[c];
	if (sam[v].longest + 1 == sam[x].longest)
	{
		sam[z].shortest = sam[x].longest + 1;
		sam[z].slink = x;
		return z;
	} // 参见附录图2
	int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink);
	sam[x].shortest = sam[y].longest + 1;
	sam[x].slink = y;
	sam[z].shortest = sam[y].longest + 1;
	sam[z].slink = y;
	while (~v && sam[v].trans[c] == x)
	{
		sam[v].trans[c] = y;
		v = sam[v].slink;
	}
	sam[y].shortest = sam[sam[y].slink].longest + 1;
	return z; // 参见附录图3
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s", s+1);
	int u = newnode(0,0,0,-1);
	int i = 1;
	while(s[i])
	{
		u = insert(s[i], u);
		++i;
	}
	ll ans = 0;
	for (i = 1;i<n; i++)
	{
		ans += sam[i].longest - sam[i].shortest + 1;
	}
	printf("%lld", ans);
	return 0;
}

line 7
n 是sam节点个数, sam的节点标号从0开始(sam[0]是sam的起点状态)

line 12
trans[i]表示当前sam节点读取i+'a'之后跳转到sam的哪个节点.slink是后缀link, 此乃sam本身必须的2个字段

line 13
2个业务字段, longest表示一个状态节点最长的子串长度, shortest表示一个状态节点最短的子串长度, 从而
longest-shortest+1就是该节点表示的等价类中包含的子串个数, 为什么说是业务字段? 因为本题就是要求不同
子串的个数,所以每个节点要有这两个字段. 如果是处理字符串的别的具体问题, 则这两个业务字段是不需要的——即
非sam本身必须字段

line 14
为什么要开两倍节点? 因为看下面的add_char方法就知道每次升级改造SAM的时候, 至少要新增一个节点z, 而且
遇到要分裂的情况的时候, 还会新诞生一个节点, 也就是每次至少产生2个节点, 所以需要开2倍的空间

line 16
新建一个sam节点, 并返回此节点的标号

line 22
则最后sam的节点就是[0,...,n-1], 其中0是自动机起点

line 25
u是s[1,..,i]所属的sam节点标号, ch 是当前读入的字符,则我们就要对SAM进行升级改造, 称升级改造之前的
sam为sam(i)（表示读入S[i]并改造完毕的sam）. 函数返回S[1,...,i+1]所属于的节点

line 28
因为新建的这个节点z就是 S[1,...,i+1] 这个子串属于的节点,当前来讲,最长肯定是i+1, 其实就是
u=S[1,..,i]所属的sam节点的最长（即i）+1

line 30
v沿着slink-path(u)往0走

line 32
因为sam[v].trans[c]是-1, 表示v节点中的子串读入c之后在sam(i)中无路可走, 那么就只能走到z去(因为根据
【1】中提及的推论, v节点中的子串读入字符c, 都将跑到同一个、别的等价类中去,而这个等价类在sam(i)中找不
到)

line 35
如果整条slink-path(u)上——从u跑到0(sam起点)所有的状态节点读入c之后在sam(i)中都找不到节点收容, 则都
跑到z去了

line 37
说明z节点中最短的子串长度就是1

line 38
只有删光了S[1,..,i+1]中所有的字符才能发生状态转移(即endpos集合才会发生变化, 这里的描述可以参见
【1】), 而且是转移到sam起点0

line 39
改造完毕,返回结果

line 41
slink-path(u)从u开始往0走, 考察经过的每个节点读入c字符之后的状态转移情况, 伊始全是-1,但是突然冒出
一个x,  即-1,-1,....,-1,x 即slink-path上突然有节点v读入c之后有路可走了,并且路是从v读入c之后转移
到了x状态节点

line 44
这一行是下一行的推论(参见【1】的推论)

line 45
我们考虑z的slink的定义——根据【1】, 不就是不停的删减字符之后第一次发生质变的时候跳转到的状态吗? 而在
slink-path(u)上v之前的节点读入c之后都是跳到z(因为在sam(i)中找不到归宿), 说明一直没有质变. 而到了v
的时候, 读入c之后就是跳到x而不是跳到-1了. 这说明发生了质变, 所以按slink的定义, 我们有 slink(z) =
x, 但是我们得问一下x有没有因为ch的读入发生变化呢? 正因为如此, 我们才要判断一下sam[v].longest + 1
与sam[x].longest之间的关系, 注意, 根据【1】的推论, 我们知道sam[v].longest+1<=sam[x].longest.
所以sam[v].longest+1和sam[x].longest之间的关系只有==与<, 如果是==的话, 则说明状态x并没有因为ch
的读入而变化, 如果是<的话, 则说明x状态因为ch的读入而变化了————确切讲是x要分裂了, 因为x中比较短的一部分
子串已经可以出现在i+1位置了(即endpos集合中新增了i+1),而比较长的那些字符串依旧不能在i+1位置出现(即
endpos集合中没有i+1) , 所以endpos不相等了, 出现了断层, 所以不再在一个等价类中了, 所以x要分裂了.

line 48
拆分x（需要拆分的原因见第45行代码）,而且注意, x和y的trans是一样的哈, 这本质也是【1】的推论决定的.

line 49
从x拆出一个节点y, 然后剩下的部分留作x, 因为剩下的部分到y的长度是连续递减的, 所以剩下的部分作为节点的
slink应该指向y

line 51
下一行代码的推论

line 52
根据slink的定义. 因为我们想知道z的slink指向谁的话, 就要不断的将S[1,...,i+1]删减字符, 直至发生质变
(这里的描述见【1】).而S[1,..,i+1]删减字符其实就是S[1,..,i]删减字符,删完再拼接一个字符S[i+1], 而
S[1,..,i]其实是slink-path(u)上节点代表的子串集合的不交并. 但是v之前的节点删完字符再拼上S[i+1]都一
直是跳到z的(参见32行代码).并没有发生质变, 只是在v这里发生了质变——跳到了y（注意, x已经因为ch的读入而
发生了分裂,所以是跳到y,而不是x了）.所以 sam[z].slink = y

line 53
将沿着 slink-path(u), 从v继续出发往0走. 将原先转移到x的都改成转移到y

line 58
根据【1】的推论

line 68
0索引不用, 因为根据上面的论述, 我们的前缀都是S[1,..,i], 所以索引都是从1开始的

line 69
初始化sam起点0,该节点里面的子串仅有空串,所以shortest、longest都是0.

line 73
每次读入一个字符,升级改造既有sam

line 76
防止答案爆int