关于广义后缀自动机

约束

tar[x][c]：SAM 转移

pre[x]：常用名有 link、fail 等 （反正就那个东西）

len[x]：结点 x 代表的最长字符串的长度

---

广义后缀自动机（下文用广义 SAM 指代），即用多个字符串的后缀建出的一个后缀自动机，拥有和后缀自动机相似的性质。

有三种较流传广泛的广义后缀自动机写法：

1. 插入新字符串时将 last 重置（last = 1）

SAM 插入时有用到一个 last 来记录上一个字符的结点，将其重置即回到了最初未插入任何字符的状态。看似很符合逻辑，但实际上构建出来的自动机会有问题。问题就在于原来的结点可能会被新创建的结点覆盖，并最终影响答案。

首先这道模板题肯定是卡不掉，因为本题只和结点信息（pre 和 len ）有关系。我们在建立这种错误的广义 SAM 时并没有覆盖任何结点的 pre 和 len 。但让我们来看这样一道题（改自 P3804）：

给定 $N$ 个字符串，求这 $N$ 个字符串的出现次数不为 1 连续子串的（出现次数 * 字符串长度）的最大值。

这道题需要用到一个基本的拓扑排序，然后这种假广义 SAM 就会挂掉，具体说明见 dalao 的博客。假广义 SAM 由于出现了奇怪的空结点在这里就会挂掉。写份简单的代码演示一下。

假 SAM 解法

这份代码把 n 改成 1 后是可以 直接通过 P3804 的。然后我们来给一组数据：

2
aaab
aaaab

嗯，代码输出了 8，但是很显然 aa 在两个字符串中一共出现了 5 次，因此最大值应该是 2*5=14 。现在很显然这种构建方法是错误的了。

2. 使用 Trie 树建自动机

这种方法很好理解，即离线把所有的字符串构建成一棵 Trie 树，然后再把各个字符（即 Trie 树上各个结点）插入到 SAM 里面时，last 设置为它在 Trie 树上的父亲对应的 SAM 上的结点。这样做的正确性是显然的，但显然并不等于易证。具体还是可以看看上面那篇博客来着。

AC 代码

3. 在线构建

嗯，重头戏来了。然后具体分析还是可以看上面那篇博客。

简单来说，就是我们在插入字符串时需要看一下当前准备插入的位置是否已经有结点了，如果有的话我们只需要在其基础上额外判断一下拆分 SAM 结点的情况没；否则的话就和普通的 SAM 插入一模一样了。贴一下代码。

附：在线文本比对工具

前置：

inline int create(int l) {
	len[++tot] = l;
	return tot;
}

普通的 SAM 插入：

inline void operator+=(int c) {
	int i = lst;
	lst = create(len[i]+1);
	while (!tar[i][c]) {
		tar[i][c] = lst;
		if (!(i = pre[i])) return (void)(pre[lst] = 1);
	}
	const int ori = tar[i][c];
	if (len[i]+1==len[ori]) return (void)(pre[lst] = ori);
	const int sub = create(len[i]+1);
	memcpy(tar[sub], tar[ori], sizeof(tar[0]));
	pre[sub] = pre[ori];
	pre[lst] = pre[ori] = sub;
	do {
		tar[i][c] = sub;
		i = pre[i];
	} while (i && tar[i][c]==ori);
}

在线的广义 SAM 插入：

inline void operator+=(int c) {
	int i = lst;
	if (tar[i][c]) { // 如果已经有结点了
		const int ori = tar[i][c];
		if (len[i]+1==len[ori]) return (void)(lst = ori);
		const int sub = create(len[i]+1);
		memcpy(tar[sub], tar[ori], sizeof(tar[0]));
		pre[sub] = pre[ori];
		lst = pre[ori] = sub;
		do {
			tar[i][c] = sub;
			i = pre[i];
		} while (i && tar[i][c]==ori);
	} else { // ... 否则创建新的结点
		lst = create(len[i]+1);
		while (!tar[i][c]) {
			tar[i][c] = lst;
			if (!(i = pre[i])) return (void)(pre[lst] = 1);
		}
		const int ori = tar[i][c];
		if (len[i]+1==len[ori]) return (void)(pre[lst] = ori);
		const int sub = create(len[i]+1);
		memcpy(tar[sub], tar[ori], sizeof(tar[0]));
		pre[sub] = pre[ori];
		pre[lst] = pre[ori] = sub;
		do {
			tar[i][c] = sub;
			i = pre[i];
		} while (i && tar[i][c]==ori);
	}
}

嗯，然后我们发现这段代码重复了很多。于是我们把它抽离出来变成了这样：

inline void operator+=(int c) {
	int i = lst;
	int &ope = tar[i][c]? lst: pre[lst = create(len[i]+1)];
	while (!tar[i][c]) { // 对于已经 tar[i][c] 不为零的情况，这段代码根本不会执行，因此没有影响
		tar[i][c] = lst;
		if (!(i = pre[i])) return (void)(ope = 1);
	}
	const int ori = tar[i][c];
	if (len[i]+1==len[ori]) return (void)(ope = ori);
	const int sub = create(len[i]+1);
	memcpy(tar[sub], tar[ori], sizeof(tar[0]));
	pre[sub] = pre[ori];
	ope = pre[ori] = sub;
	do {
		tar[i][c] = sub;
		i = pre[i];
	} while (i && tar[i][c]==ori);
}

嗯，完美！和普通的 SAM 插入就差了几行，然后我们就可以愉快的做这道题了。

// Mivik 2020.8.21
#include <mivik.h>

#ifdef MIVIK
MI cin(popen("xsel -ob", "r"));
#else
MI cin;
#endif

typedef long long qe;

const int nmax = 1000001;
const int cmax = 26;

template<typename T> inline bool getmax(T& a, const T& b) { return a<b && (a = b, true); }

struct _ {
	const static int S = nmax*2;
	int tar[S][cmax], pre[S], len[S], too[nmax], seq[S], cnt[S];
	int lst = 1, tot = 1;
	int n;
	inline int create(int l) {
		len[++tot] = l;
		return tot;
	}
	inline void operator+=(int c) {
		int i = lst;
		int &ope = tar[i][c]? lst: pre[lst = create(len[i]+1)];
		while (!tar[i][c]) {
			tar[i][c] = lst;
			if (!(i = pre[i])) return (void)(ope = 1);
		}
		const int ori = tar[i][c];
		if (len[i]+1==len[ori]) return (void)(ope = ori);
		const int sub = create(len[i]+1);
		memcpy(tar[sub], tar[ori], sizeof(tar[0]));
		pre[sub] = pre[ori];
		ope = pre[ori] = sub;
		do {
			tar[i][c] = sub;
			i = pre[i];
		} while (i && tar[i][c]==ori);
	}
	inline qe solve() {
		int i;
		qe ret = 0;
		for (i=2;i<=tot;i++) ret += len[i]-len[pre[i]];
		return ret;
	}
} sam;
int main() {
	int n = R;
	char c;
	while (n--) {
		cin>c;
		sam.lst = 1;
		while (c!=-1 && !isspace(c)) {
			sam += c-'a';
			++sam.cnt[sam.lst];
			c = cin.get();
		}
		getmax(sam.n, sam.len[sam.lst]);
	}
	cout<sam.solve()<endl;
	return 0;
}