在这篇文章中，我将描述一种解决最大公共子串问题的算法。假设我们正在尝试解密加密的二进制数据，首先让我们尝试通过搜索最大的子字符串来找到常见模式。
输入字符串示例：
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
我们正在寻找重复两次的字符串：
数据头??
前缀
首先，我们编写一个方法来比较两个字符串的前缀，让它返回结果字符串，其中左前缀的字符与右前缀的字符相等。
例如，对于以下行：
val lhs = "asdfWUKI"
val rhs = "asdfIKUW"
结果字符串 –阿斯达夫
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)
}
暴力破解
当事情进展不顺利时，你应该诉诸暴力。使用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??
??
?
我们通过排序来解决
让我们对后缀数组进行排序，然后循环遍历当前元素在左手（左）、下一个在右手（右）的所有元素，并使用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
