Arreglo de sufijos

Recursos
Fuente	Recurso	Notas
CF	Suffix Array	Videos y problemas de práctica
cp-algo	Suffix Array - Definition & Construction
CPC	11 - Strings (Suffix Array)
CP2	6.6 - Suffix Array and Applications

El arreglo de sufijos de un string es el arreglo ordenado de todos los sufijos posibles del string. Cada sufijo suele representarse por su índice de inicio.

Por ejemplo, si nuestro string fuera abcbcba, el arreglo de sufijos sería el siguiente:

Sufijo	String
6	`a`
0	`abcbcba`
5	`ba`
3	`bcba`
1	`bcbcba`
4	`cba`
2	`cbcba`

Construcción

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Suffix Array	Fácil	Suffix Array	en el módulo

La filosofía general detrás de la construcción de un arreglo de sufijos es ordenar de forma incremental. Primero empezamos comparando el primer carácter de cada sufijo, y luego duplicamos la cantidad que comparamos hasta estar comparando toda la longitud del string. Si esto suena muy abstracto, no hay problema: todos los detalles de implementación se desarrollan abajo.

Transformación inicial

Por conveniencia, empecemos agregando un “carácter nulo” al final del string. Esto actúa como desempate y garantiza que nunca lleguemos al final de un sufijo al comparar dos sufijos. $ o el carácter espacio son opciones posibles, ya que el código ASCII de cualquiera de los dos es menor que a.

Para evitar problemas de desborde de índices, también concatenaremos el string consigo mismo. Nótese que, como cualquier comparación se habría detenido en el carácter nulo, esto no tiene efecto sobre el orden del arreglo de sufijos.

Después de implementar estas dos transformaciones, los strings que comparamos se verían así (siguiendo con abcbcba como ejemplo):

Sufijo	String
7	`$abcbcba`
6	`a$abcbcba`
0	`abcbcba$abcbcba`
5	`ba$abcbcba`
3	`bcba$abcbcba`
1	`bcbcba$abcbcba`
4	`cba$abcbcba`
2	`cbcba$abcbcba`

El último sufijo que empieza con $ siempre irá primero; no importa especialmente.

Ordenamiento

Como se dijo antes, primero consideremos solo el primer carácter de cada subcadena y ordenémoslo:

Sufijo	String
7	`$abcbcba`
0	`abcbcba$abcbcba`
6	`a$abcbcba`
1	`bcbcba$abcbcba`
3	`bcba$abcbcba`
5	`ba$abcbcba`
2	`cbcba$abcbcba`
4	`cba$abcbcba`

A partir de aquí empezamos a duplicar la longitud del string que comparamos. Para llegar al punto en que comparamos sufijos de forma eficiente, hagamos primero un poco de análisis.

Digamos que acabamos de ordenar todos los sufijos por los primeros $2$ caracteres, y ahora estamos comparando los primeros cuatro caracteres de los sufijos $2$ y $4$ :

Sufijo	String
2	`cbcb`
4	`cba$`

Si los primeros $2$ caracteres del sufijo $2$ ya eran menores o mayores que los del sufijo $4$ , no cambia nada. Sin embargo, en este caso no lo son; vamos a tener que comparar la mitad derecha.

¿Cómo podríamos hacer esto? Bueno, lo interesante es que, como acabamos de ordenar todos los sufijos por los primeros $2$ , ¡ya tenemos información sobre las mitades derechas! La mitad derecha de los primeros cuatro caracteres del sufijo $2$ es simplemente los primeros dos caracteres del sufijo $4$ . De forma similar, la mitad derecha del sufijo $4$ son los primeros dos caracteres del sufijo $6$ .

Para comparar estas mitades de sufijo, después de cada iteración de ordenamiento podemos asignar a cada sufijo a medio hornear un número que representa su posición en el arreglo. Si dos sufijos a medio hornear son iguales, entonces recibirían el mismo número. Estos números suelen llamarse clases de equivalencia .

Aplicando este aumento a nuestro arreglo ordenado por el primer carácter, ahora tendríamos:

Clase de eq.	Sufijo	String
0	7	`$abcbcba`
1	0	`abcbcba$abcbcba`
1	6	`a$abcbcba`
2	1	`bcbcba$abcbcba`
2	3	`bcba$abcbcba`
2	5	`ba$abcbcba`
3	2	`cbcba$abcbcba`
3	4	`cba$abcbcba`

Optimización

Como estamos haciendo $\mathcal{O}(N \log N)$ ordenamientos $\log N$ veces, nuestro algoritmo actual es $\mathcal{O}(N \log^2 N)$ .

Aunque esto es adecuado, a veces puede ser un poco lento, especialmente cuando crear un arreglo de sufijos es a menudo solo el primer paso en muchos problemas. ¡Por suerte, podemos arreglarlo! Como todo lo que comparamos está en el rango $[0, N)$ , podemos usar radix sort para quitar un factor logarítmico de nuestra complejidad.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++Java


#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
void radix_sort(vector<pair<pair<int, int>, int>> &arr) {
	// con radix sort, en realidad hay que ordenar primero por el segundo elemento
	for (int i : vector<int>{2, 1}) {
		auto key = [&](const pair<pair<int, int>, int> &x) {
			return i == 1 ? x.first.first : x.first.second;
		};
		int max = 0;
		for (const auto &i : arr) { max = std::max(max, key(i)); }
		vector<int> occs(max + 1);
		for (const auto &i : arr) { occs[key(i)]++; }
		vector<int> start(max + 1);
		for (int i = 1; i <= max; i++) { start[i] = start[i - 1] + occs[i - 1]; }
 
		vector<pair<pair<int, int>, int>> new_arr(arr.size());
		for (const auto &i : arr) {
			new_arr[start[key(i)]] = i;
			start[key(i)]++;
		}
		arr = new_arr;
	}
}
 
int main() {
	std::string str;
	std::cin >> str;
	str += '$';
	const int n = str.size();  // solo una abreviatura
 
	vector<pair<pair<int, int>, int>> suffs(n);
	for (int i = 0; i < n; i++) { suffs[i] = {{str[i], str[i]}, i}; }
	std::sort(suffs.begin(), suffs.end());
	vector<int> equiv(n);
	for (int i = 1; i < n; i++) {
		auto [c_val, cs] = suffs[i];
		auto [p_val, ps] = suffs[i - 1];
		equiv[cs] = equiv[ps] + (c_val > p_val);
	}
 
	for (int cmp_amt = 1; cmp_amt < n; cmp_amt *= 2) {
		for (auto &[val, s] : suffs) {
			// los números de orden de la mitad izquierda y derecha respectivamente
			val = {equiv[s], equiv[(s + cmp_amt) % n]};
		}
		// sin la optimización de radix sort, usaríamos `std::sort`
		radix_sort(suffs);
 
		// asignar números a los sufijos recién ordenados
		for (int i = 1; i < n; i++) {
			auto [c_val, cs] = suffs[i];
			auto [p_val, ps] = suffs[i - 1];
			equiv[cs] = equiv[ps] + (c_val > p_val);
		}
	}
 
	for (int i = 1; i < n; i++) { cout << suffs[i].second << " \n"[i == n - 1]; }
}

Más abajo hay también una implementación más compacta.

Recursos
Fuente	Recurso	Notas
Benq	Suffix Array w/ LCP	O(N log N)


import java.io.*;
import java.util.*;
import java.util.function.Function;
 
public class SuffixArray {
	static class Suffix implements Comparable<Suffix> {
		public int start;
		public int leftEq;
		public int rightEq;
 
		public Suffix(int start, int leftEq, int rightEq) {
			this.start = start;
			this.leftEq = leftEq;
			this.rightEq = rightEq;
		}
 
		@Override
		public int compareTo(Suffix o) {
			return leftEq != o.leftEq ? leftEq - o.leftEq : rightEq - o.rightEq;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		String str = read.readLine() + '$';
		final int n = str.length();  // solo una abreviatura
 
		Suffix[] suffs = new Suffix[n];
		for (int i = 0; i < n; i++) {
			suffs[i] = new Suffix(i, str.charAt(i), str.charAt(i));
		}
		Arrays.sort(suffs);
		int[] equiv = new int[n];
		for (int i = 1; i < n; i++) {
			Suffix curr = suffs[i], prev = suffs[i - 1];
			boolean gt = curr.compareTo(prev) > 0;
			equiv[curr.start] = equiv[prev.start] + (gt ? 1 : 0);
		}
 
		for (int cmpAmt = 1; cmpAmt < n; cmpAmt *= 2) {
			for (Suffix s : suffs) {
				s.leftEq = equiv[s.start];
				s.rightEq = equiv[(s.start + cmpAmt) % n];
			}
			radixSort(suffs);
 
			for (int i = 1; i < n; i++) {
				Suffix curr = suffs[i], prev = suffs[i - 1];
				boolean gt = curr.compareTo(prev) > 0;
				equiv[curr.start] = equiv[prev.start] + (gt ? 1 : 0);
			}
		}
 
		for (int i = 1; i < n; i++) {
			System.out.print(suffs[i].start);
			System.out.print(i == n - 1 ? '\n' : ' ');
		}
	}
 
	private static void radixSort(Suffix[] arr) {
		for (int i : Arrays.asList(2, 1)) {
			Function<Suffix, Integer> key = x -> (i == 1 ? x.leftEq : x.rightEq);
			int max = 0;
			for (Suffix s : arr) { max = Math.max(max, key.apply(s)); }
 
			int[] occs = new int[max + 1];
			for (Suffix s : arr) { occs[key.apply(s)]++; }
			int[] start = new int[max + 1];
			for (int j = 1; j <= max; j++) { start[j] = start[j - 1] + occs[j - 1]; }
 
			Suffix[] newArr = new Suffix[arr.length];
			for (Suffix s : arr) {
				newArr[start[key.apply(s)]] = s;
				start[key.apply(s)]++;
			}
 
			for (int j = 0; j < arr.length; j++) { arr[j] = newArr[j]; }
		}
	}
}

Se recomienda también probar la implementación contra una solución de fuerza bruta para muchos strings pequeños.

Aquí hay un script pequeño que imprime un caso de prueba y su respuesta:

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int n = 50;  // adjust n as you please
	vector<char> str;
	for (int i = 0; i < n; i++) { str.push_back('a' + rand() % 26); }
 
	for (char c : str) { cout << c; }
	cout << '\n';
 
	vector<int> suffs(n);
	for (int i = 0; i < n; i++) { suffs[i] = i; }
	std::sort(suffs.begin(), suffs.end(), [&](int a, int b) {
		vector<char> a_vec(str.begin() + a, str.end());
		vector<char> b_vec(str.begin() + b, str.end());
		return a_vec < b_vec;
	});
 
	for (int i = 0; i < n; i++) { cout << suffs[i] << " \n"[i == n - 1]; }
}


import java.io.*;
import java.util.*;
 
public class Generator {
	public static void main(String[] args) throws IOException {
		Random rng = new Random();
 
		int n = 50;  // adjust n as you please
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) { sb.append((char)('a' + rng.nextInt(26))); }
		String str = sb.toString();
		System.out.println(str);
 
		Integer[] suffs = new Integer[n];  // Integer is needed for comparators
		for (int i = 0; i < n; i++) { suffs[i] = i; }
		Arrays.sort(suffs, Comparator.comparing(i -> str.substring(i, n)));
 
		for (int i = 0; i < n; i++) {
			System.out.print(suffs[i]);
			System.out.print(i == n - 1 ? '\n' : ' ');
		}
	}
}


from random import choice
from string import ascii_lowercase
 
n = 50  # adjust n as you please
str_ = [choice(ascii_lowercase) for _ in range(n)]
 
print("".join(str_))
 
suffs = list(range(n))
suffs.sort(key=lambda s: str_[s:])
 
print(" ".join(str(i) for i in suffs))

Arreglo LCP

El arreglo LCP es un arreglo auxiliar habitual basado en el arreglo de sufijos que guarda el prefijo común más largo (LCP) entre elementos adyacentes del arreglo de sufijos.

Tomando nuestro string de ejemplo de arriba, tal arreglo se vería así:

LCP	Sufijo	String
NA	7	`$abcbcba`
0	0	`abcbcba$abcbcba`
1	6	`a$abcbcba`
0	1	`bcbcba$abcbcba`
3	3	`bcba$abcbcba`
1	5	`ba$abcbcba`
0	2	`cbcba$abcbcba`
2	4	`cba$abcbcba`

Cada fila contiene el LCP entre el string de la fila y el de la fila anterior.

Construcción

Un algoritmo que se usa a menudo para construir este arreglo LCP empieza calculando el LCP del sufijo que empieza en $0$ y su sufijo anterior. Luego calcula el LCP del sufijo que empieza en $1$ y su sufijo anterior, y así sucesivamente. El motivo de este orden de cálculo es poder aplicar una optimización ingeniosa que se describe mejor con nuestro ejemplo.

Digamos que acabamos de calcular el LCP de la fila del sufijo $3$ . Nuestro siguiente paso, entonces, sería calcular el LCP del sufijo $4$ .

Uno podría pensar que tendríamos que empezar a comparar los prefijos de nuevo para este sufijo, ¡pero en realidad no hace falta! Recordemos que acabamos de calcular que el LCP de los sufijos $3$ y $1$ es de $3$ caracteres, lo que significa que los sufijos $4$ y $2$ , y todos los sufijos entre ellos en el arreglo (aunque en nuestro ejemplo no haya ninguno) deben tener al menos $2$ caracteres en común.

Esto significa que podemos empezar a comparar desde el tercer carácter para calcular el LCP de la fila del sufijo $4$ , en lugar de empezar de cero.

En general, mantenemos una variable $\texttt{start\\_at}$ que guarda la cantidad de caracteres comunes que sabemos que el sufijo actual tiene con su predecesor en el arreglo de sufijos. Esta variable nos dice cuántos caracteres podemos saltar, porque sabemos que son iguales. Después de cada cálculo de un LCP, fijamos esta variable en su valor menos uno, excepto cuando el LCP ya es $0$ .

Se verá una implementación de este algoritmo en la siguiente sección.

Aplicación

Ahora que construimos este arreglo LCP, veamos una aplicación.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Number of Substrings	Fácil	Suffix Array	en el módulo

Una observación crucial para este problema es que toda subcadena se puede representar como un prefijo de algún sufijo. Sabemos que el sufijo $i$ tiene $N-i$ (recordemos que $N$ es la longitud del string) prefijos posibles.

Nótese que la cantidad de prefijos del sufijo $i$ que son duplicados es simplemente el prefijo común más largo entre $i$ y su predecesor. Con esto, podemos iterar por el arreglo LCP y calcular nuestra respuesta de una sola pasada.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++Java


#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
 
// BeginCodeSnip{Radix Sort}
void radix_sort(vector<pair<pair<int, int>, int>> &arr) {
	for (int i : vector<int>{2, 1}) {
		auto key = [&](const pair<pair<int, int>, int> &x) {
			return i == 1 ? x.first.first : x.first.second;
		};
		int max = 0;
		for (const auto &i : arr) { max = std::max(max, key(i)); }
		vector<int> occs(max + 1);
		for (const auto &i : arr) { occs[key(i)]++; }
		vector<int> start(max + 1);
		for (int i = 1; i <= max; i++) { start[i] = start[i - 1] + occs[i - 1]; }
 
		vector<pair<pair<int, int>, int>> new_arr(arr.size());
		for (const auto &i : arr) {
			new_arr[start[key(i)]] = i;
			start[key(i)]++;
		}
		arr = new_arr;
	}
}
// EndCodeSnip
 
int main() {
	string str;
	std::cin >> str;
	str += '$';
	const int n = str.size();
 
	// BeginCodeSnip{Suffix Array Computation}
	vector<pair<pair<int, int>, int>> suffs(n);
	for (int i = 0; i < n; i++) { suffs[i] = {{str[i], str[i]}, i}; }
	std::sort(suffs.begin(), suffs.end());
	vector<vector<int>> equiv{vector<int>(n)};
	for (int i = 1; i < n; i++) {
		auto [c_val, cs] = suffs[i];
		auto [p_val, ps] = suffs[i - 1];
		equiv[0][cs] = equiv[0][ps] + (c_val > p_val);
	}
 
	int cmp_amt = 1;
	while (cmp_amt < n) {
		const vector<int> &prev = equiv.back();
		for (auto &[val, s] : suffs) { val = {prev[s], prev[(s + cmp_amt) % n]}; }
		radix_sort(suffs);
 
		vector<int> nxt_eq = vector<int>(n);
		for (int i = 1; i < n; i++) {
			auto [c_val, cs] = suffs[i];
			auto [p_val, ps] = suffs[i - 1];
			nxt_eq[cs] = nxt_eq[ps] + (c_val > p_val);
		}
		equiv.push_back(nxt_eq);
 
		cmp_amt *= 2;
	}
	// EndCodeSnip
 
	vector<int> suff_ind(n);
	for (int i = 0; i < n; i++) { suff_ind[suffs[i].second] = i; }
	vector<int> lcp(n - 1);
	int start_at = 0;  // la variable de la que se habló en la explicación
	for (int i = 0; i < n - 1; i++) {
		int prev = suffs[suff_ind[i] - 1].second;
		int curr_cmp = start_at;
		while (str[i + curr_cmp] == str[prev + curr_cmp]) { curr_cmp++; }
		lcp[suff_ind[i] - 1] = curr_cmp;
		start_at = std::max(curr_cmp - 1, 0);
	}
 
	long long diff_substrings = 0;
	for (int i = 0; i < lcp.size(); i++) {
		// restamos 1 por el carácter nulo
		diff_substrings += n - 1 - i - lcp[i];
	}
	cout << diff_substrings << endl;
}


import java.io.*;
import java.util.*;
import java.util.function.Function;
 
public class SuffixArray {
	// BeginCodeSnip{Suffix Class}
	static class Suffix implements Comparable<Suffix> {
		public int start;
		public int leftEq;
		public int rightEq;
 
		public Suffix(int start, int leftEq, int rightEq) {
			this.start = start;
			this.leftEq = leftEq;
			this.rightEq = rightEq;
		}
 
		@Override
		public int compareTo(Suffix o) {
			return leftEq != o.leftEq ? leftEq - o.leftEq : rightEq - o.rightEq;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		String str = read.readLine() + '$';
		final int n = str.length();
 
		// BeginCodeSnip{Suffix Array Computation}
		Suffix[] suffs = new Suffix[n];
		for (int i = 0; i < n; i++) {
			suffs[i] = new Suffix(i, str.charAt(i), str.charAt(i));
		}
		Arrays.sort(suffs);
		int[] equiv = new int[n];
		for (int i = 1; i < n; i++) {
			Suffix curr = suffs[i], prev = suffs[i - 1];
			boolean gt = curr.compareTo(prev) > 0;
			equiv[curr.start] = equiv[prev.start] + (gt ? 1 : 0);
		}
 
		for (int cmpAmt = 1; cmpAmt < n; cmpAmt *= 2) {
			for (Suffix s : suffs) {
				s.leftEq = equiv[s.start];
				s.rightEq = equiv[(s.start + cmpAmt) % n];
			}
			radixSort(suffs);
 
			for (int i = 1; i < n; i++) {
				Suffix curr = suffs[i], prev = suffs[i - 1];
				boolean gt = curr.compareTo(prev) > 0;
				equiv[curr.start] = equiv[prev.start] + (gt ? 1 : 0);
			}
		}
		// EndCodeSnip
 
		int[] suffInd = new int[n];
		for (int i = 0; i < n; i++) { suffInd[suffs[i].start] = i; }
		int[] lcp = new int[n - 1];
		int startAt = 0;  // la variable de la que se habló en la explicación
		for (int i = 0; i < n - 1; i++) {
			int prev = suffs[suffInd[i] - 1].start;
			int currCmp = startAt;
			while (str.charAt(i + currCmp) == str.charAt(prev + currCmp)) { currCmp++; }
			lcp[suffInd[i] - 1] = currCmp;
			startAt = Math.max(currCmp - 1, 0);
		}
 
		long diffSubstrings = 0;
		for (int i = 0; i < lcp.length; i++) {
			// restamos 1 por el carácter nulo
			diffSubstrings += n - 1 - i - lcp[i];
		}
		System.out.println(diffSubstrings);
	}
 
	// BeginCodeSnip{Radix Sort}
	private static void radixSort(Suffix[] arr) {
		for (int i : Arrays.asList(2, 1)) {
			Function<Suffix, Integer> key = x -> (i == 1 ? x.leftEq : x.rightEq);
			int max = 0;
			for (Suffix s : arr) { max = Math.max(max, key.apply(s)); }
 
			int[] occs = new int[max + 1];
			for (Suffix s : arr) { occs[key.apply(s)]++; }
			int[] start = new int[max + 1];
			for (int j = 1; j <= max; j++) { start[j] = start[j - 1] + occs[j - 1]; }
 
			Suffix[] newArr = new Suffix[arr.length];
			for (Suffix s : arr) {
				newArr[start[key.apply(s)]] = s;
				start[key.apply(s)]++;
			}
 
			for (int j = 0; j < arr.length; j++) { arr[j] = newArr[j]; }
		}
	}
	// EndCodeSnip
}

Transformada de Burrows-Wheeler

Recursos
Fuente	Recurso	Notas
GFG	Inverting Burrows-Wheeler Transform	¿se podría simplificar?

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	String Transform	Difícil	Suffix Array	Solución

Enumerar runs

Recursos
Fuente	Recurso	Notas
cp-algo	Finding repetitions	¿se podría simplificar?

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Run Enumerate	Difícil	Suffix Array	—

Problemas

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Platinum	Standing Out from the Herd	Difícil	Suffix Array	—
	CF	Two Prefixes	Difícil	Suffix Array	—