Estructuras de sufijos de strings

int N, sa[MN], ctr;  // longitud del string, arreglo de sufijos, contador
 
struct Edge {
  public:
	int n, l, r;  // nodo, la arista cubre s[l..r]
	explicit operator bool() const { return n != -1; }
} c[MN * 2][26];  // aristas de un árbol de sufijos
 
void dfs(int n = 0, int d = 0) {
	bool c = 0;  // Tiene hijo. Si es false, este nodo es una hoja
	for (int i = 0; i < 26; ++i)
		if (c[n][i]) {
			c = 1;
			dfs(c[n][i].n, d + c[n][i].r - c[n][i].l);
		}
	if (!c) sa[ctr++] = N - d;
}

int N;
char s[MN];
int sa[MN];   // arreglo de sufijos
int lcp[MN];  // lcp[i] guarda el prefijo común más largo entre s[sa[i-1]..]
              // y s[sa[i]..]
 
Edge c[MN * 2][MK];  // aristas del árbol de sufijos
int d[MN * 2];       // longitud del string correspondiente a un nodo del árbol
int q[MN * 2], Q, ctr,
    rm[MN];  // q se usa como pila. ctr cuenta nodos del árbol
std::stack<int> ins[MN];
void build_tree() {
	q[0] = N;
	Q = 0;
	for (int i = N - 1; i >= 1; --i) {
		while (Q && lcp[q[Q]] > lcp[i]) --Q;
		if (lcp[q[Q]] != lcp[i])
			++rm[q[Q]];  // Cota derecha del rango donde lcp es el prefijo
			             // común más largo
		q[++Q] = i;
	}
	q[0] = 0, Q = 0;
	for (int i = 1; i < N; ++i) {
		while (Q && lcp[q[Q]] > lcp[i]) --Q;
		if (lcp[q[Q]] != lcp[i])
			ins[q[Q]].push(i);  // Cota izquierda del rango donde lcp se
			                    // vuelve por primera vez un prefijo común más largo
		q[++Q] = i;
	}
	// Las cotas izquierda y derecha calculadas arriba se pueden interpretar
	// como el preorden y postorden DFS
	q[0] = 0, Q = 0;  // Este arreglo q ahora guarda la pila de ancestros de
	                  // cada nodo nuevo creado
	auto nn = [&](int l, int dd) {
		++ctr;
		d[ctr] = dd;
		int p = q[Q];
		// p es el padre de este nodo, por definición de la pila q
		int r = l + dd;
		// s[l..r] es el string correspondiente al nodo que estamos insertando
		l += d[p];
		// d[p] es la longitud del padre, así que s[l..l+d[p]] ya estaría
		// cubierto por los ancestros del nodo
		c[p][s[l]] = {ctr, l, r};
		return ctr;
	};
	for (int i = 0; i < N; ++i) {
		Q -= rm[i];
		for (int x; !ins[i].empty(); ins[i].pop()) {
			x = ins[i].top();
			x = nn(sa[x], lcp[x]);
			//   sa[x+1] sería equivalente, por definición de lcp
			q[++Q] = x;
		}
		nn(sa[i], N - sa[i]);
	}
}

char s[MN];          // string
int ord[MN];         // nodos que representan prefijos del string s
int u[MN * 2];       // si el nodo ya se creó
int l[MN * 2];       // enlace en el autómata de sufijos
Edge c[MN * 2][27];  // arista del árbol de sufijos (no del autómata; la
                     // estructura del autómata no es necesaria para construir
                     // el stree)
void build_tree() {
	s[N] = 26;  // terminador
	for (int i = N; i >= 0; --i) ord[i] = append(ord[i + 1], s[i]);
	for (int i = 0, x, r, l; i <= N; ++i) {
		x = ord[i], r = N + 1;
		for (; x && !u[x]; x = l[x]) {
			l = r - d[x] + d[l[x]];
			c[l[x]][s[l]] = {x, l, r};
			r = l;
			u[x] = 1;
		}
	}
}