后缀自动机 ( SuffixAutomaton )

网上很多讲解2333… 我觉得我也没有完全理解清楚….
主要就是 $next$ 数组的求解 分三种情况
贴个板子

#include <bits/stdc++.h>
const int maxn = 2e6 + 10;
int a[maxn], c[maxn], size[maxn];
long long ans;
namespace SuffixAutomaton{
	int start, last, nodecnt;
	struct node{
		int trans[26], next, max, min();
	}T[maxn];
	int node::min(){
		return T[next].max + 1;
	}
	int newnode(int max = 0){
		T[++nodecnt].max = max; return nodecnt;
	}
	int init(){
		start = last = newnode();
	}
	int expend(int c){
		int u = newnode(T[last].max + 1), v = last; size[u] = 1;
		for (; v && !T[v].trans[c]; v = T[v].next) T[v].trans[c] = u;
		if(!v) T[u].next = start;
		else {
			int o = T[v].trans[c];
			if (T[v].max + 1 == T[o].max) T[u].next = o;
			else {
				int n = newnode(T[v].max + 1);
				memcpy(T[n].trans, T[o].trans, sizeof(T[n].trans));
				T[n].next = T[o].next; T[o].next = T[u].next = n;
				for (; v && T[v].trans[c] == o; v = T[v].next) T[v].trans[c] = n;
			}
		}return last = u;
	}
	void calc(){
		for (int i = 1; i <= nodecnt; i++) c[T[i].max]++;
		for (int i = 1; i <= nodecnt; i++) c[i] += c[i-1];
		for (int i = nodecnt; i; i--) a[c[T[i].max]--] = i;
		for (int i = nodecnt; i; i--){
			int p = a[i];
			size[T[p].next] += size[p];
			if(size[p] > 1)ans = std::max(ans, 1LL * size[p] * T[p].max);
		}
		printf("%lld\n", ans);
	}
}using namespace SuffixAutomaton;
char s[maxn];
int main(){
	init();
	scanf("%s", s); int n = strlen(s);
	for(int i = 0; s[i]; i++)
		expend(s[i] - 'a'); 
	calc();
	return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦