Tag Archives: lcs

最長の共通部分文字列

この投稿では、最大共通部分文字列問題を解決するためのアルゴリズムについて説明します。暗号化されたバイナリ データを復号化しようとしているとします。まず、最大の部分文字列を検索して共通のパターンを見つけてみましょう。
入力文字列の例:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
2 回繰り返される文字列を探しています。
データヘッダー??

プレフィックス

まず、2 つの文字列の接頭辞を比較するメソッドを作成しましょう。左側の接頭辞の文字が右側の接頭辞の文字と等しい結果の文字列を返します。
たとえば、行の場合は次のようになります。

        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 メソッドを使用して、文字列を 2 つのループで処理します。最初のループでは i から最後までの文字列を取得し、2 番目のループでは 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
}

サフィックス配列

より洗練されたソリューションには、「Suffix Array」と呼ばれるデータ構造というツールが必要です。このデータ構造は、ループ内に埋められた部分文字列の配列であり、各部分文字列は行の次の文字から始まり、最後まで続きます。
たとえば、次の行の場合:

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