Substring comum mais longa

Neste post descreverei um algoritmo para resolver o maior problema comum de substring. Digamos que estamos tentando descriptografar dados binários criptografados. Primeiro, vamos tentar encontrar padrões comuns procurando pela maior substring.
Exemplo de string de entrada:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Estamos procurando uma string que se repete duas vezes:
CABEÇALHO DE DADOS??

Prefixos

Primeiro, vamos escrever um método para comparar os prefixos de duas strings, deixe-o retornar a string resultante na qual os caracteres do prefixo esquerdo são iguais aos caracteres do prefixo direito.
Por exemplo, para as linhas:

        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

Sequência de resultados – asdf
Exemplo em Kotlin:

fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Força Bruta

Quando as coisas não funcionam bem, você deve recorrer à força bruta. Usando o método mais longoPrefix, percorreremos a string em dois loops, o primeiro leva a string de i até o final, o segundo de i + 1 até o final, passa-os adiante para procurar o maior prefixo. A complexidade de tempo deste algoritmo é aproximadamente O(n^2) ~ O(n*^3).
Exemplo em Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Matriz de sufixos

Para uma solução mais elegante, precisamos de uma ferramenta - uma estrutura de dados chamada “Suffix Array”. Esta estrutura de dados é uma matriz de substrings preenchidas em um loop, onde cada substring começa no próximo caractere da linha até o final.
Por exemplo, para a linha:

adasDATAHEADER??

A matriz de sufixos é semelhante a esta:

adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

Resolvemos classificando

Vamos classificar o array de sufixos, depois percorrer todos os elementos em um loop onde o elemento atual está na mão esquerda (lhs), o próximo está na mão direita (rhs) e calcular o prefixo mais longo usando o longPrefix método.
Exemplo em Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

A complexidade de tempo do algoritmo é O(N log N), o que é muito melhor do que uma solução simples.

Fontes

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Código fonte

https://gitlab.com/demensdeum/algorithms