[题解] [Mivik 的字符串公开赛] 大佬语录

给定字符串 $S$，多次询问，每次给出字符串 $T$，问 $S$ 有多少个本质不同的字串以 $T$ 结尾。

题目链接

---

思路

满分做法

我们考虑到以某个字符串结尾的字符串就是它对应的节点在后缀自动机的 fail 树上的子树内所有节点的长度和。于是我们先建出后缀自动机，然后统计一下子树内的长度和（不包括自己），最后查询时再加上 $(maxlen - len + 1)$ 即可。

mivik.h

代码

// Mivik 2020.10.18
#include <mivik.h>

MI cin;

using std::string;

typedef long long qe;

const int nmax = 1000001;
const int S = nmax * 2;
const int cmax = 26;

template<> struct Q<string> { inline void operator()(MI &r, string &t) {
	t.clear(); char c = r.read<char>();
	while (c != -1 && !isspace(c)) { t += c; c = r.get(); }
} };

namespace sam {
int tar[S][cmax], len[S], pre[S], too[nmax], seq[S];
qe sum[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);
	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 void init() {
	const int n = len[lst];
	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;
	for (int i = tot; i > 1; --i) {
		const int x = seq[i];
		sum[pre[x]] += sum[x] + len[x] - len[pre[x]];
	}
}
inline qe solve(const string &str) {
	int cur = 1;
	for (char c : str) if (!(cur = tar[cur][c - 'a'])) return 0;
	return sum[cur] + len[cur] - str.size() + 1;
}
} // namespace sam

int main() {
	for (char c : cin.read<string>()) sam::extend(c - 'a');
	sam::init();
	for (int q = R; q; --q)
		cout < sam::solve(cin.read<string>()) < endl;
}