{"id":2469,"date":"2020-01-01T15:03:07","date_gmt":"2020-01-01T12:03:07","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2469"},"modified":"2024-12-16T22:32:30","modified_gmt":"2024-12-16T19:32:30","slug":"longest-common-substring","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/pt\/2020\/01\/01\/longest-common-substring\/","title":{"rendered":"Substring comum mais longa"},"content":{"rendered":"

Neste post descreverei um algoritmo para resolver o maior problema comum de substring. Digamos que estamos tentando descriptografar dados bin\u00e1rios criptografados. Primeiro, vamos tentar encontrar padr\u00f5es comuns procurando pela maior substring.
Exemplo de string de entrada:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf<\/strong>
Estamos procurando uma string que se repete duas vezes:
CABE\u00c7ALHO DE DADOS??<\/strong><\/p>\n

Prefixos<\/h3>\n

Primeiro, vamos escrever um m\u00e9todo para comparar os prefixos de duas strings, deixe-o retornar a string resultante na qual os caracteres do prefixo esquerdo s\u00e3o iguais aos caracteres do prefixo direito.
Por exemplo, para as linhas:<\/p>\n

\n
        val lhs = \"asdfWUKI\"\n        val rhs = \"asdfIKUW\"\n\n<\/code><\/pre>\n<\/div>\n
Sequ\u00eancia de resultados – asdf
Exemplo em Kotlin:<\/p>\n
\n
fun longestPrefix(lhs: String, rhs: String): String {\n        val maximalLength = min(lhs.length-1, rhs.length -1)\n        for (i in 0..maximalLength) {\n            val xChar = lhs.take(i)\n            val yChar = rhs.take(i)\n                if (xChar != yChar) {\n                    return lhs.substring(0, i-1)\n                }\n        }\n        return lhs.substring(0,maximalLength)\n}\n\n<\/code><\/pre>\n<\/div>\n
For\u00e7a Bruta<\/h3>\n
Quando as coisas n\u00e3o funcionam bem, voc\u00ea deve recorrer \u00e0 for\u00e7a bruta. Usando o m\u00e9todo mais longoPrefix, percorreremos a string em dois loops, o primeiro leva a string de i at\u00e9 o final, o segundo de i + 1 at\u00e9 o final, passa-os adiante para procurar o maior prefixo. A complexidade de tempo deste algoritmo \u00e9 aproximadamente O(n^2) ~ O(n*^3).
Exemplo em Kotlin:<\/p>\n
\n
fun searchLongestRepeatedSubstring(searchString: String): String {\n        var longestRepeatedSubstring = \"\"\n        for (x in 0..searchString.length-1) {\n            val lhs = searchString.substring(x)\n            for (y in x+1..searchString.length-1) {\n                val rhs = searchString.substring(y)\n                val longestPrefix = longestPrefix(lhs, rhs)\n                if (longestRepeatedSubstring.length < longestPrefix.length) {\n                    longestRepeatedSubstring = longestPrefix\n                }\n            }\n        }\n        return longestRepeatedSubstring\n}\n\n<\/code><\/pre>\n<\/div>\n
Matriz de sufixos<\/h3>\n
Para uma solu\u00e7\u00e3o mais elegante, precisamos de uma ferramenta - uma estrutura de dados chamada \u201cSuffix Array\u201d. Esta estrutura de dados \u00e9 uma matriz de substrings preenchidas em um loop, onde cada substring come\u00e7a no pr\u00f3ximo caractere da linha at\u00e9 o final.
Por exemplo, para a linha:<\/p>\n
\n
adasDATAHEADER??\n\n<\/code><\/pre>\n<\/div>\n
A matriz de sufixos \u00e9 semelhante a esta:<\/p>\n
\n
adasDATAHEADER??\ndasDATAHEADER??\nasDATAHEADER??\nsDATAHEADER??\nDATAHEADER??\nATAHEADER??\nTAHEADER??\nAHEADER??\nHEADER??\nEADER??\nADER??\nDER??\nER??\nR??\n??\n?\n\n<\/code><\/pre>\n<\/div>\n
Resolvemos classificando<\/h3>\n
Vamos classificar o array de sufixos, depois percorrer todos os elementos em um loop onde o elemento atual est\u00e1 na m\u00e3o esquerda (lhs), o pr\u00f3ximo est\u00e1 na m\u00e3o direita (rhs) e calcular o prefixo mais longo usando o longPrefix m\u00e9todo.
Exemplo em Kotlin:<\/p>\n
\n
fun searchLongestRepeatedSubstring(searchString: String): String {\n    val suffixTree = suffixArray(searchString)\n    val sortedSuffixTree = suffixTree.sorted()\n\n    var longestRepeatedSubstring = \"\"\n    for (i in 0..sortedSuffixTree.count() - 2) {\n        val lhs = sortedSuffixTree[i]\n        val rhs = sortedSuffixTree[i+1]\n        val longestPrefix = longestPrefix(lhs, rhs)\n        if (longestRepeatedSubstring.length < longestPrefix.length) {\n            longestRepeatedSubstring = longestPrefix\n        }\n    }\n    return longestRepeatedSubstring\n}\n\n<\/code><\/pre>\n<\/div>\n
A complexidade de tempo do algoritmo \u00e9 O(N log N), o que \u00e9 muito melhor do que uma solu\u00e7\u00e3o simples.<\/p>\n
Fontes<\/h3>\n
https:\/\/en.wikipedia.org\/wiki\/Longest_common_substring_problem<\/a> <\/p>\n
C\u00f3digo fonte<\/h3>\n
https:\/\/gitlab.com\/demensdeum\/algorithms<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Neste post descreverei um algoritmo para resolver o maior problema comum de substring. Digamos que estamos tentando descriptografar dados bin\u00e1rios criptografados. Primeiro, vamos tentar encontrar padr\u00f5es comuns procurando pela maior substring.Exemplo de string de entrada:adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdfEstamos procurando uma string que se repete duas vezes:CABE\u00c7ALHO DE DADOS?? Prefixos Primeiro, vamos escrever um m\u00e9todo para comparar os prefixosContinue reading “Substring comum mais longa”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,140,141],"class_list":["post-2469","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-lcs","tag-suffix-array","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"pt","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2469","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=2469"}],"version-history":[{"count":16,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2469\/revisions"}],"predecessor-version":[{"id":3926,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2469\/revisions\/3926"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=2469"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=2469"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=2469"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}