1

たとえば、次のような文字列のペアがあります。abcabcabcandabcxxxabcと共通部分文字列ペア (LCSP) のリスト。この場合abc、最初の文字列の 3 つが 2 番目の文字列の 2 つにマップされるため、LCSP は 6 つのペアabcです。ここで、ペアの最長の有効な (インクリメントする) シーケンスを見つける必要があります。この場合、3 つの等しい長さの解があり 0:0,3:6; 0:0,6:6; 3:0,6:6ます。 」）。これを最長部分文字列ペア シーケンスまたは LSPQ と呼びます。（Qは文字列とシーケンスを混同しないでください）

この例の LCSP は次のとおりです。

LCSP('abcabcabc', 'abcxxxabc') = 
[ [ 6, 6, 3 ],
  [ 6, 0, 3 ],
  [ 3, 6, 3 ],
  [ 0, 6, 3 ],
  [ 3, 0, 3 ],
  [ 0, 0, 3 ] ]


LSPQ(LCSP('abcabcabc', 'abcxxxabc'), 0, 0, 0) = 
   [ { a: 0, b: 0, size: 3 }, { a: 3, b: 6, size: 3 } ]

今、私は総当たりで再帰的にすべての組み合わせを試して見つけました。そのため、約 25 ペアに制限されています。それ以外の場合は非現実的です。Size=[10,15,20,25,26,30], Time ms = [0,15,300,1000,2000,19000]

より長い入力 LCSP (共通部分文字列ペアのリスト) を使用できるように、線形時間または少なくとも 2 次複雑さでそれを行う方法はありますか。

この問題は「Longest Common Subsequence」に似ていますが、正確には違います。入力は 2 つの文字列ではなく、長さで並べ替えられた共通部分文字列のリストだからです。そのため、既存のソリューションをどこで探すべきか、または存在するかどうかさえわかりません。

ここに私の特定のコード（JavaScript）があります：

function getChainSize(T) {
    var R = 0
    for (var i = 0; i < T.length; i++) R += T[i].size
    return R
}
function LSPQ(T, X, Y, id) {
  // X,Y are first unused character is str1,str2
  //id is current pair
    function findNextPossible() {
        var x = id
        while (x < T.length) {
            if (T[x][0] >= X && T[x][1] >= Y) return x
            x++
        }
        return -1
    }
    var id = findNextPossible()
    if (id < 0) return []
    var C = [{a:T[id][0], b:T[id][1], size:T[id][2] }]
    // with current
    var o = T[id]
    var A = C.concat(LSPQ(T, o[0]+o[2], o[1]+o[2], id+1))
    // without current
    var B = LSPQ(T, X, Y, id+1)
    if (getChainSize(A) < getChainSize(B)) return B
    return A
}
4

0 に答える 0