「Luogu P2408」不同子串个数

Description

给你一个长为 (n) 的字符串，求不同的子串的个数。

我们定义两个子串不同，当且仅当有这两个子串长度不一样，或者长度一样且有任意一位不一样。

子串的定义：原字符串中连续的一段字符组成的字符串。

Hint

• 对于 (30\%) 的数据，(1le nle 10^3)
• 对于 (100\%) 的数据，(1le nle 10^5)

Solution 1

本质不同的子串计数问题，后缀自动机（SAM）。

我们先复习一下 SAM 的一些性质：

• 一个关于字符串 (s) 的 SAM 包含了 (s) 所有子串 的信息。
• SAM 中的一条路径对应 (s) 的一个子串，反过来，(s) 的一个子串也对应 SAM 的一条路径。简而言之，SAM 上的路径与字符串的子串都是一一对应的。
• SAM 的一个状态对应一些字符串的集合，这个集合的元素都各自对应初始状态到该状态的一条路径。

根据这些性质，我们不难得出一个结论：一个字符串的所有本质不同的子串的个数，等于其 SAM 上初始状态到所有非初始状态的路径数。

众所周知 SAM 是一个 DAG（有向无环图），那么答案也是 这个 DAG 上以初始状态对应的结点为起点的路径数。

都扯到 DAG 了，不考虑 dp 一下？

设 (f(x)) 为以 (x) 为起点的路径条数，那么答案就是 (f( ext{start}))。（( ext{start}) 指初始状态的结点）

状态转移方程显而易见：

[f(x) = 1 + sumlimits_{ ext{Edge}(x ightarrow y) in ext{DAG}} f(y) ]

其中，若 SAM 中存在一个转移 (delta(x, c) = y)，那么 DAG 上就对应一条边 (x ightarrow y)。

注意空串不算，所以答案在输出前要减去一

时间复杂度 (O(nlog |Sigma|))， 空间复杂度 (O(n))。（SAM 用 map 实现，dp 的过程用记忆化搜索实现）

Code for Solution 1

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : Luogu P2408 不同子串个数
 */
#include <iostream>
#include <map>
#include <string>

using namespace std;
const int N = 1e5 + 5;

namespace SAM {
	const int T = N << 1;
	struct Node {
		map<char, int> ch;
		int link, len;
	} t[T];
	int total, last;
	
	inline void extend(char c) {
		int p = last, np = last = ++total;
		t[np].len = t[p].len + 1;
		
		for (; p && !t[p].ch.count(c); p = t[p].link)
			t[p].ch[c] = np;
		
		if (!p) {
			t[np].link = 1;
		} else {
			int q = t[p].ch[c];
			if (t[q].len == t[p].len + 1) {
				t[np].link = q;
			} else {
				int nq = ++total;
				t[nq].ch = t[q].ch, t[nq].link = t[q].link;
				t[nq].len = t[p].len + 1;
				t[np].link = t[q].link = nq;
				while (p && t[p].ch.count(c) && t[p].ch[c] == q)
					t[p].ch[c] = nq, p = t[p].link;
			}
		}
	}
	void init(string& s) {
		total = last = 1;
		for (string::iterator p = s.begin(); p != s.end(); p++)
			extend(*p);
	}
	
	long long f[T];
	long long solve(int x);
};

long long SAM::solve(int x = 1) {
	if (f[x]) return f[x];
	f[x] = 1ll;
	for (map<char, int>::iterator it = t[x].ch.begin(); it != t[x].ch.end(); it++)
		f[x] += solve(it->second);
	return f[x];
}

int n;
string s;

signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> s;
	SAM::init(s);
	cout << SAM::solve() - 1 << endl;
	return 0;
}

Solution 2

仍然是 SAM 。

上述算法是 离线 的，无法动态维护。而有一道题 Luogu P4070 [SDOI2016]生成魔咒 就要求使用在线算法。

当 SAM extend 这个字符之后，答案会增大。

由 ( ext{link}) 的定义可知，一个结点 (x) 对应的子串长度范围为 ([ ext{len}( ext{link}(x)) + 1, ext{len}(i)])

于是，添加一个字符，答案会增加 ( ext{len}(p) - ext{len}( ext{link}(p))) 这么多。

于是就做到了动态维护答案。

注意，因为拆点而新建的结点对答案没有影响，不能算进去。

时空复杂度同 Solution 1。

Code for Solution 2

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : Luogu P2408 不同子串个数
 */
#include <iostream>
#include <map>
#include <string>

using namespace std;
const int N = 1e5 + 5;

namespace SAM {
	const int T = N << 1;
	struct Node {
		map<char, int> ch;
		int link, len;
	} t[T];
	
	int total, last;
	long long ans = 0ll;
	
	inline void extend(char c) {
		int p = last, np = last = ++total;
		t[np].len = t[p].len + 1;
		
		for (; p && !t[p].ch.count(c); p = t[p].link)
			t[p].ch[c] = np;
		
		if (!p) {
			t[np].link = 1;
		} else {
			int q = t[p].ch[c];
			if (t[q].len == t[p].len + 1) {
				t[np].link = q;
			} else {
				int nq = ++total;
				t[nq].ch = t[q].ch, t[nq].link = t[q].link;
				t[nq].len = t[p].len + 1;
				t[np].link = t[q].link = nq;
				while (p && t[p].ch.count(c) && t[p].ch[c] == q)
					t[p].ch[c] = nq, p = t[p].link;
			}
		}
		ans += t[np].len - t[t[np].link].len;
	}
	void init(string& s) {
		total = last = 1;
		for (string::iterator p = s.begin(); p != s.end(); p++)
			extend(*p);
	}
};

int n;
string s;

signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> s;
	SAM::init(s);
	cout << SAM::ans << endl;
	return 0;
}