В данной заметке я опишу алгоритм решения задачи наибольшей общей подстроки. Допустим мы пытаемся расшифровать зашифрованные бинарные данные, для начала попробуем найти общие паттерны с помощью поиска наибольшей подстроки.
Входная строка для примера:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Мы ищем повторяющуюся дважды строку:
DATAHEADER??
Префиксы
Для начала напишем метод для сравнения префиксов двух строк, пусть возвращает результирующую строку в которой символы левого префикса равны символам правого префикса.
Например для строк:
val lhs = "asdfWUKI"
val rhs = "asdfIKUW"
Результирующая строка – asdf
Пример на 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)
}
Brute Force
Когда не получается по хорошему, стоит прибегнуть к грубой силе. Используя метод longestPrefix пройдем по строке двумя циклами, первый берет строку от i до конца, второй от i + 1 до конца, передает их в поиск наибольшего префикса. Временная сложность данного алгоритма примерно равна O(n^2) ~ O(n*^3).
Пример на 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
}
Суффиксный массив
Для более элегантного решения нам потребуется инструмент - структура данных под названием “Суффиксный массив”. Данная структура данных представляет из себя массив из подстрок заполняемых в цикле, где каждая подстрока начинается со следующего символа строки до конца.
Например для строки:
adasDATAHEADER??
Суффиксный массив выглядит так:
adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?
Решаем сортировкой
Отсортируем суффиксный массив, затем пройдем по всем элементам циклом где в левой руке (lhs) текущий элемент, в правой (rhs) следующий и вычислим самый длинный префикс с помощью метода longestPrefix.
Пример на 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
}
Временная сложность алгоритма O(N log N), что гораздо лучше решения в лоб.
Источники
https://en.wikipedia.org/wiki/Longest_common_substring_problem
Исходный код
https://gitlab.com/demensdeum/algorithms