Algoritmo para construir uma matriz de sufixos no tempo

Ultimamente, tenho trabalhado com matrizes de sufixos e não consigo encontrar um algoritmo eficiente para criar uma matriz de sufixos fácil de entender. Eu já vi em muitos sites que existe uma$O(n \log^2 n)$algoritmo, mas não consigo entender, pois muitos detalhes importantes são omitidos. Há um exemplo no Top Coder .

Alguém poderia me apresentar um algoritmo eficiente para construção de matriz de sufixos, que é fácil de entender?

Você pode calcular a matriz de sufixos em tempo linear com o algoritmo DC-3 . Este é um algoritmo sofisticado super legal que pode ser implementado em 50 linhas de código C ++ legível - um dos meus favoritos de todos os tempos. O código fonte está contido no documento original. Se você puder comparar dois caracteres em tempo constante e o tamanho do alfabeto for$n^{O(1)}$, o algoritmo DC3 é executado em $O(n)$ Tempo.

Observe que você também pode obter a árvore do sufixo em tempo linear quando tiver acesso ao array de sufixos e ao array LCP. A matriz LCP também pode ser construída com o algoritmo DC3.

Aqui está uma boa explicação para o $O(n\log^2n)$algoritmo: http://www.stanford.edu/class/cs97si/suffix-array.pdf . Na verdade, usando a classificação de tempo linear, a mesma abordagem fornece$O(n\log n)$ complexidade do tempo.

Se você tiver alguma pergunta específica sobre isso, não hesite em perguntar.

Eu concordo com A. Schultz que o DC-3 é super legal. Também não é muito complicado, mas o$O(n\log^2 n)$ ainda é mais simples.