節(jié)點(diǎn) \(u\) 對(duì)應(yīng)的：
子串?dāng)?shù)量為 \(len(u) - len(link(u))\)
所有后綴的長度為 \(\frac{len(u) * (len(u) + 1)}{2}\)

時(shí)間復(fù)雜度：建立自動(dòng)機(jī) \(O(n)\)

https://www.luogu.com.cn/problem/P3804

給定字符串 \(s\)，求出 \(s\) 的所有出現(xiàn)次數(shù)不為 1 的子串的出現(xiàn)次數(shù)乘上該子串長度的最大值。

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
struct SAM{
	static constexpr int N = 1e6;
	struct node{
		int len, link, nxt[26];
		int siz;
	}t[N << 1];
	int cntNodes;
	SAM(){
		cntNodes = 1;
		fill(t[0].nxt, t[0].nxt + 26, 1);
		t[0].len = -1;
	}
	int extend(int p, int c){
		if (t[p].nxt[c]){
			int q = t[p].nxt[c];
			if (t[q].len == t[p].len + 1){
				return q;
			}
			int r = ++ cntNodes;
			t[r].siz = 0;
			t[r].len = t[p].len + 1;
			t[r].link = t[q].link;
			copy(t[q].nxt, t[q].nxt + 26, t[r].nxt);
			t[q].link = r;
			while (t[p].nxt[c] == q){
				t[p].nxt[c] = r;
				p = t[p].link;
			}
			return r;
		}
		int cur = ++ cntNodes;
		t[cur].len = t[p].len + 1;
		t[cur].siz = 1;
		while (!t[p].nxt[c]){
			t[p].nxt[c] = cur;
			p = t[p].link;
		}
		t[cur].link = extend(p, c);
		return cur;
	}
};
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	string s;
	cin >> s;
	
	SAM sam;
	int p = 1;
	for (auto c : s){
		p = sam.extend(p, c - 'a');
	}
	
	vector<vector<int>> G(sam.cntNodes + 1);
	for (int i = 2; i <= sam.cntNodes; i ++ ){
		G[sam.t[i].link].push_back(i);
	}
	LL ans = 0;
	function<void(int)> dfs = [&](int u){
		for (auto v : G[u]){
			dfs(v);
			sam.t[u].siz += sam.t[v].siz;
		}
		if (sam.t[u].siz > 1){
			ans = max(ans, 1LL * sam.t[u].siz * sam.t[u].len);
		}
	};
	dfs(1);
	cout << ans << "\n";
	return 0;
}

https://codeforc.es/problemset/problem/1780/G
找出出現(xiàn)次數(shù)可以被串長度整除的串的數(shù)量
https://codeforc.es/problemset/problem/616/F
計(jì)算出現(xiàn)次數(shù)長度權(quán)重最大