广义 SAM 15 pts 求调悬关
  • 板块灌水区
  • 楼主haochengw920
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/12 22:27
  • 上次更新2024/5/13 13:31:19
查看原帖
广义 SAM 15 pts 求调悬关
563650
haochengw920楼主2024/5/12 22:27

rt

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;

const int MAXN = 1000005;

int n, ans;
char s[MAXN];

class Suffix_automaton {
	public : 
	int root, cnt;
	private : 
	struct Node {
		int len, fail;
		int sons[28];
	}tr[MAXN << 1]; int lst;
	inline int NewNode(int ln) {
		tr[++ cnt].len = ln;
		tr[cnt].fail = 0;
		memset(tr[cnt].sons, 0, sizeof(tr[cnt].sons));
		return cnt;
	} 
	public : 
	inline Node& operator [] (const int &x) {
		return tr[x];
	} 
	inline void Init() {
		root = lst = NewNode(0); 
	}
	inline void Upd() {
		lst = 1;
	}
	inline void Insert(int x) {
		int p = lst;
		int &u = tr[p].sons[x] ? lst : tr[lst = NewNode(tr[p].len + 1)].fail;
		while (p && !tr[p].sons[x])
			tr[p].sons[x] = lst, p = tr[p].fail;
		if (!p) u = 1;
		else {
			int q = tr[p].sons[x]; 
			if (tr[q].len == tr[p].len + 1) 
				u = q; 
			else {
				int nq = NewNode(tr[p].len + 1);
				tr[nq].fail = tr[q].fail;
				memcpy(tr[nq].sons, tr[q].sons, sizeof(tr[q].sons));
				u = tr[q].fail = nq;
				while (p && tr[p].sons[x] == q)
					tr[p].sons[x] = nq, p = tr[p].sons[x];
			}
		}
	}
}SAM;

signed main()
{
	scanf ("%lld", &n);
	SAM.Init(); 
	for (int i = 1; i <= n; ++ i) {
		scanf ("%s", s + 1);
		SAM.Upd(); 
		for (int j = 1; s[j] != '\0'; ++ j)
			SAM.Insert(s[j] - 'a');
	}
	for (int i = 2; i <= SAM.cnt; ++ i)
		ans += SAM[i].len - SAM[SAM[i].fail].len; 
	printf ("%lld\n%lld\n", ans, SAM.cnt);
	return 0;
}
2024/5/12 22:27
加载中...