Tag Archives: lcs

Dans cet article, je décrirai un algorithme permettant de résoudre le plus grand problème de sous-chaîne courant. Supposons que nous essayions de décrypter des données binaires chiffrées. Essayons d’abord de trouver des modèles communs en recherchant la plus grande sous-chaîne.
Exemple de chaîne d’entrée :
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Nous recherchons une chaîne qui se répète deux fois :
EN-TÊTE DE DONNÉES ??

Préfixes

Tout d’abord, écrivons une méthode pour comparer les préfixes de deux chaînes, laissons-la renvoyer la chaîne résultante dans laquelle les caractères du préfixe de gauche sont égaux aux caractères du préfixe de droite.
Par exemple, pour les lignes :

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

Chaîne de résultat – asdf
Exemple en 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)
}

Force Brute

Lorsque les choses ne fonctionnent pas bien, vous devriez recourir à la force brute. En utilisant la méthode longestPrefix, nous allons parcourir la chaîne en deux boucles, la première prend la chaîne de i à la fin, la seconde de i + 1 à la fin, les transmet pour rechercher le plus grand préfixe. La complexité temporelle de cet algorithme est d’environ O(n^2) ~ O(n*^3).
Exemple en 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
}

Tableau de suffixes

Pour une solution plus élégante, nous avons besoin d'un outil : une structure de données appelée "Suffix Array". Cette structure de données est un tableau de sous-chaînes remplies dans une boucle, où chaque sous-chaîne commence du caractère suivant de la ligne jusqu'à la fin.
Par exemple, pour la ligne :

adasDATAHEADER??

Le tableau de suffixes ressemble à ceci :

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

On résout en triant

Trions le tableau de suffixes, puis parcourons tous les éléments dans une boucle où l'élément actuel est dans la main gauche (à gauche), le suivant est dans la main droite (à droite) et calculons le préfixe le plus long en utilisant le plus longPrefix méthode.
Exemple en 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
}

La complexité temporelle de l'algorithme est O(N log N), ce qui est bien meilleur qu'une solution simple.

Sources

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

Code source

https://gitlab.com/demensdeum/algorithms