[题解] [Mivik 的字符串公开赛] 求和

给定字符串 $S$，求 $S$ 所有非空子串的本质不同子串个数之和。

$1\le|S|\le 2\cdot10^5$

题目链接

---

思路

Subtask 1

仅由一种字符构成的长度为 $i$ 的字符串的本质不同子串个数是 $i$。那么我们直接列出式子：

$$
ans=\sum_{i=1}^n (n-i+1)\cdot i
$$

求出并取模即可。

满分做法

我们对于每一个本质不同的字符串考虑原字符串有多少个子串包含了它。我们借用后缀自动机中 $endpos$ 的概念（即一个子串在原字符串中右端点出现位置的集合）。假设一个子串的 $endpos$ 是 ${2,5}$，而它的长度为 1，原字符串长度为 8。那么我们发现，对于原字符串的每一个位置 $i$，以该位置作为右端点且包含这个子串的子串个数 $f_i$ 分别是：

i	1	2	3	4	5	6	7	8
$f_i$	0	2	2	2	5	5	5	5

我们发现，$f_i$ 的值是一个由很多连续段组成的序列，且每一个连续段的左端点都属于 $endpos$ 集合。更形式化地，我们这样描述这个序列（下面用 $endpos_i$ 代表 $endpos$ 中第 $i$ 大的元素，记 $endpos$ 集合的大小为 $m$）：

$$ f_i=[0,0,0,0,\cdots\\ (endpos_1-maxlen+1),(endpos_1-maxlen+1),\cdots\\ (endpos_2-maxlen+1),(endpos_2-maxlen+1),\cdots\cdots\\ (endpos_k-maxlen+1),(endpos_k-maxlen+1)] $$

于是我们考虑在后缀自动机上 set 启发式合并维护 $endpos$ 集合，并实时维护 $f_i$ 的和，然后统计即可。

代码

mivik.h

// Mivik 2020.10.18
#include <mivik.h>

#include <cassert>
#include <set>

MI cin;

using std::set;
using std::string;

typedef long long qe;

const int $n = 200001;
const int S = $n * 2;
const int $c = 26;
const int mod = 1000000007;

inline int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
inline void Add(int &x, int y) {
	if ((x += y) >= mod) x -= mod;
}
inline void Sub(int &x, int y) {
	if ((x -= y) < 0) x += mod;
}

int n, lst[S], pre[S], tar[S];
#define go(x) for (int b = ::lst[x], v = ::tar[b]; b; v = ::tar[b = ::pre[b]])

namespace sam {
int tar[S][$c], len[S], pre[S], too[$n], seq[S];
int sum[S];
set<int> w[S];
int lst = 1, tot = 1;
inline int node(int l) {
	len[++tot] = l;
	return tot;
}
inline void extend(int c) {
	int i = lst;
	lst = node(len[i] + 1);
	w[lst].insert(len[lst]);
	while (!tar[i][c]) {
		tar[i][c] = lst;
		if (!(i = pre[i])) return (void)(pre[lst] = 1);
	}
	const int o = tar[i][c];
	if (len[i] + 1 == len[o]) return (void)(pre[lst] = o);
	const int s = node(len[i] + 1);
	memcpy(tar[s], tar[o], sizeof(tar[0]));
	pre[s] = pre[o];
	pre[lst] = pre[o] = s;
	do {
		tar[i][c] = s;
		i = pre[i];
	} while (i && tar[i][c] == o);
}
inline qe calc(int x) { return ((qe)x * (x + 1)) >> 1; }
inline void merge(int x, int y) {
	if (w[x].size() < w[y].size()) {
		std::swap(w[x], w[y]);
		std::swap(sum[x], sum[y]);
	}
	for (int v : w[y]) {
		auto iter = w[x].lower_bound(v);
		assert(iter == w[x].end() || *iter != v);
		if (w[x].empty())
			;
		else if (iter == w[x].end())
			Add(sum[x], (qe)(n - v + 1) * (v - *--w[x].end()) % mod);
		else if (iter == w[x].begin()) {
			const int t = *w[x].begin();
			Add(sum[x], (qe)(n - t + 1) * (t - v) % mod);
		} else {
			const int l = *std::prev(iter), r = *iter;
			Sub(sum[x], (qe)(n - r + 1) * (r - l) % mod);
			Add(sum[x], (qe)(n - r + 1) * (r - v) % mod);
			Add(sum[x], (qe)(n - v + 1) * (v - l) % mod);
		}
		w[x].insert(v);
	}
}
inline int solve() {
	for (int i = 1; i <= tot; ++i) ++too[len[i]];
	for (int i = 1; i <= n; ++i) too[i] += too[i - 1];
	for (int i = 1; i <= tot; ++i) seq[too[len[i]]--] = i;
	int ans = 0;
	for (int i = tot; i > 1; --i) {
		const int x = seq[i];
		if (w[x].empty()) continue;
		const int b = *w[x].begin(), cnt = n - b + 1, l = len[x] - len[pre[x]];
		const int rsum = add(sum[x], (qe)cnt * (b - len[x] + 1) % mod);
		Add(ans, add((qe)rsum * l % mod, (qe)cnt * calc(l - 1) % mod));
		merge(pre[x], x);
	}
	return ans;
}
} // namespace sam

int main() {
	char c = cin.read<char>();
	while (c != -1 && !isspace(c)) {
		sam::extend(c - 'a');
		c = cin.get();
	}
	n = sam::len[sam::lst];
	cout < sam::solve() < endl;
}