文字列中で最長類似サブシーケンスを見つける

Question

サブシーケンスの前半が後半と同じように最長サブシーケンスを探したいとします。

例：abkcjadfbckという文字列の場合、abcabcは最初と後半で繰り返されるため、結果はabcabcとなります。攪拌中に結果はaaです。

Answer 1

このタスクは、2つのよく知られた問題の組み合わせとして扱われます。

1. サブシーケンスの2つの半分の間にある点が事前に分かっている場合は、2つの文字列の最適な一致を見つける必要があります。これはPairwise alignment問題です。様々な動的プログラミング方法がO（N ）時間でそれを解決します。
2. 文字列を最適に分割するポイントを見つけるには、Golden section searchまたはフィボナッチ検索を使用できます。これらのアルゴリズムは、O（log N）時間の複雑さを有する。

Answer 2

inputStringの最初のパスでは、各文字がどのくらいの頻度で出現するかをカウントし、出現1のものを削除できます。

input: inputString 
data strucutres: 
Set<Triple<char[], Integer, Integer>> potentialSecondWords; 
Map<Char, List<Integer>> lettersList; 

for the characters c with increasing index h in inputString do 
    if (!lettersList.get(c).isEmpty()) { 
    for ((secondWord, currentIndex, maxIndex) in potentialSecondWords) { 
     if (there exists a j in lettersList.get(c) between currentIndex and maxIndex) { 
     update (secondWord, currentIndex, maxIndex) by adding c to secondWord and replacing currentIndex with j; 
     } 
    } 
    if potentialSecondWords contains a triple whose char[] is equal to c, remove it; 
    put new Triple with value (c,lettersList.get(c).get(0), h-1) into potentialSecondWords; 
    } 
    lettersList.get(c).add(h); 
} 
find the largest secondWord in potentialSecondWords and output secondWord twice; 

したがって、このアルゴリズムは、それが理にかなって各インデックス、現在のインデックスから始まる電位第2のワードを表すトリプルための作成、アレイの上に一度通過し、すべての潜在的な第二の単語を更新します。

適切なリストの実装では、nはinputStringのサイズであり、このアルゴリズムは最悪の場合ランタイムO（n²）を持ちます。^nのために。