昨天做某道字符串题目，有这样一个需求：对于串 $s$ 的每一个位置 $x$，求出 $s$ 最长的一个后缀，使得该后缀能从 $x$ 开始完全匹配。

我瞪着屏幕抓耳挠腮了好半天，终于想到一个优秀的 SA + 并查集 + 链表 $\operatorname{O}(|s|\log |s|)$ 解法：

求出 $s$ 的 $\operatorname{height}$ 函数。如果有 $\operatorname{height}(k+1)=|s|-\operatorname{sa}(k)$（0-indexed），也即排名为 $k$ 的后缀的长就是 $\operatorname{height}(k)$，那么 $\operatorname{sa}(k)$ 就可能成为 $\operatorname{sa}(k+1),\operatorname{sa}(k+2),\cdots$ 的答案（直到延伸到 $\operatorname{height}(k+p)<|s|-\operatorname{sa}(k)$ 为止）；$\operatorname{height}(k)=|s|-\operatorname{sa}(k)$ 之于 $\operatorname{sa}(k-1),\operatorname{sa}(k-2),\cdots$ 亦然。

那么我们对 $\operatorname{height}$ 从大到小排个序，按顺序合并 $\operatorname{sa}(k),\operatorname{sa}(k+1)$ 所在连通块，然后链表保存一下连通块内没有计算答案的节点就行。

写出来把题过掉的时候感觉棒极了。SA 真是太强大辣！

然后发现这玩意就是反串的 $\operatorname{next}$ 函数。

constexpr int N = 2e5 + 10;

char s[N]; int n; pint tp[N];
int sa[N], rk[N], ht[N], p, tt[N], ta[N], mxm[N] /* x匹配的最长后缀长度 */, hlst[N];

inl void radix_sort () {
	memset (ta, 0, p + 1<<2);
	for (int i = 0; i < n; ++i) ++ta[rk[i]];
	for (int i = 1; i <= p; ++i) ta[i] += ta[i-1];
	for (int i = n-1; ~i; --i) sa[ta[rk[tt[i]]]--] = tt[i];
}
inl void build_SA () {
	p = 128;
	for (int i = 0; i < n; ++i)
		tt[i] = i, rk[i] = s[i];
	radix_sort (); sa[0] = n;
	for (int len = 1, tot = 1;; tot = len<<=1) {
		for (int i = 0; i < n; ++i) {
			tp[i] = pint (rk[i], i+len < n ? rk[i+len] : 0);
			if (sa[i+1] >= len) tt[tot++] = sa[i+1] - len;
			else tt[sa[i+1]] = n - sa[i+1] - 1;
		}
		radix_sort (); p = 0;
		for (int i = 1; i <= n; ++i)
			rk[sa[i]] = p += tp[sa[i-1]] != tp[sa[i]];
		if (p == n) break;
	}
	for (int i = 0, k = 0, q; i < n; ++i) {
		if (k) --k;
		if (rk[i] == 1) { ht[1] = 0; continue; }
		q = sa[rk[i] - 1];
		while (s[i + k] == s[q + k]) ++k;
		ht[rk[i]] = k;
	}
}

struct dsu {
	struct list_node {
		list_node *nxt; int id;
	} nde[N], *head[N], *tail[N]; int fa[N];
	inl void init () {
		for (int x = 1; x <= n; ++x)
			fa[x] = x, (head[x]=tail[x]=nde+x)->id = sa[x];
	}
	int get (int x) { return fa[x] == x ? x : fa[x] = get (fa[x]); }
	inl void merge (int x, int y) {
		if ((x = get (x)) == (y = get (y))) return;
		if (head[x] != nullptr)
			head[y] == nullptr ? head[y] = head[x]
				: tail[y]->nxt = head[x], tail[y] = tail[x];
		fa[x] = y;
	}
	inl void imple (int x, int _mxm) {
		auto ima = head[x = get (x)];
		while (ima != nullptr)
			mxm[ima->id] = _mxm, ima = ima->nxt;
		head[x] = tail[x] = nullptr;
	}
} d;

int main () {
	build_SA ();
	d.init (); iota (hlst, hlst + n - 1, 2);
	sort (hlst, hlst + n - 1, [] (int x, int y) {
		return ht[x] > ht[y]; });
	for (int i = 0, x, j, pres, _ht; i < n-1; i = j) {
		j = i, pres = -1, _ht = ht[hlst[i]];
		while (j < n-1 && ht[x = hlst[j]] == _ht)
			if (ht[x] != n - sa[x] && ht[x] != n - sa[x-1])
				d.merge (x, x - 1), ++j;
			else pres = j++;
		if (pres == -1) continue;
		x = hlst[pres];
		if (ht[x] == n - sa[x]) d.imple (x-1, ht[x]);
		else d.imple (x, ht[x]);
		d.merge (x - 1, x);
	}

	return 0;
}