Algorytm strunowy

Question

Poszukuję skutecznego algorytmu do wykonania strunyowania płytek. Zasadniczo, podano wykaz strun, powiedzmy BCD, CDE, ABC, A, a otrzymaną kafelki ciąg powinien być ABCDE, ponieważ BCD wyrównany CDE uzyskując BCDE, który jest następnie wyrównane z ABC, uzyskując ostateczny ABCDE.

Obecnie używam nieco naiwnego algorytmu, który działa w następujący sposób. Począwszy od przypadkowej pary strun, powiedzmy BCD i CDE, używam następujące (w Javie):

public static String tile(String first, String second) { 
    for (int i = 0; i < first.length() || i < second.length(); i++) { 
    // "right" tile (e.g., "BCD" and "CDE") 
    String firstTile = first.substring(i); 
    // "left" tile (e.g., "CDE" and "BCD") 
    String secondTile = second.substring(i); 
    if (second.contains(firstTile)) { 
     return first.substring(0, i) + second; 
    } else if (first.contains(secondTile)) { 
     return second.substring(0, i) + first; 
    } 
    } 
    return EMPTY; 
} 

System.out.println(tile("CDE", "ABCDEF")); // ABCDEF 
System.out.println(tile("BCD", "CDE")); // BCDE 
System.out.println(tile("CDE", "ABC")); // ABCDE 
System.out.println(tile("ABC", tile("BCX", "XYZ"))); // ABCXYZ 

Chociaż to działa, to nie jest bardzo wydajny, gdyż iteracje nad te same znaki w kółko.

Więc, czy ktoś zna lepszy (bardziej wydajny) algorytm, aby to zrobić? Ten problem jest podobny do problemu z dopasowaniem sekwencji DNA, więc wszelkie rady od kogoś z tej dziedziny (i innych, oczywiście) są bardzo mile widziane. Zauważ też, że nie szukam wyrównania, ale układanie płytek, ponieważ wymagam pełnego nakładania się jednego z ciągów nad drugim.

Obecnie szukam adaptacji Rabin-Karp algorithm, w celu poprawy asymptotycznej złożoności algorytmu, ale chciałbym usłyszeć kilka porad przed zagłębieniem się dalej w tej sprawie.

Z góry dziękuję.

---

W sytuacjach, w których nie ma niejednoznaczności - przykład {ABC, CBA} które mogłyby spowodować ABCBA lub CBABC - każdy płytki mogą być zwracane. Jednak taka sytuacja rzadko się zdarza, ponieważ układam wyrazy, np. {This is, is me} => {This is me}, które są manipulowane, aby powyższy algorytm działał.

Podobne pytanie: Efficient Algorithm for String Concatenation with Overlap

Answer 1

Pierwszą rzeczą, aby zadać to czy chcesz znaleźć Tilling z CDB, CDA {}? Nie ma jednej uprawy.

Answer 2

Myślę, że powinno to działać w przypadku układania dwóch ciągów i być bardziej wydajne niż bieżąca implementacja przy użyciu podciągów i zawiera. Koncepcyjnie przechodzę przez znaki w łańcuchu "lewym" i porównuję je do znaku w "prawym" ciągu znaków. Jeśli te dwa znaki pasują, przechodzę do następnego znaku w prawym ciągu. W zależności od tego, z którego łańcucha po raz pierwszy osiągnięto koniec, a jeśli ostatnie porównywane znaki pasują do siebie lub nie, zostanie zidentyfikowany jeden z możliwych przypadków kafelkowania.

Nie wymyśliłem niczego, co poprawiłoby złożoność czasu układania więcej niż dwóch ciągów. Jako niewielka uwaga dla wielu ciągów, poniższy algorytm można łatwo rozszerzyć, sprawdzając układanie pojedynczego "lewego" łańcucha z wieloma "prawymi" strunami naraz, co może uniemożliwić dodatkową pętlę nad strunami, jeśli próbujesz dowiedzieć się, czy robić ("ABC", "BCX", "XYZ") lub ("ABC", "XYZ", BCX "), po prostu wypróbowując wszystkie możliwości.

string Tile(string a, string b) 
{ 
    // Try both orderings of a and b, 
    // since TileLeftToRight is not commutative. 

    string ab = TileLeftToRight(a, b); 

    if (ab != "") 
     return ab; 

    return TileLeftToRight(b, a); 

    // Alternatively you could return whichever 
    // of the two results is longest, for cases 
    // like ("ABC" "BCABC"). 
} 

string TileLeftToRight(string left, string right) 
{ 
    int i = 0; 
    int j = 0; 

    while (true) 
    { 
     if (left[i] != right[j]) 
     { 
      i++; 

      if (i >= left.Length) 
       return ""; 
     } 
     else 
     { 
      i++; 
      j++; 

      if (i >= left.Length) 
       return left + right.Substring(j); 

      if (j >= right.Length) 
       return left; 
     } 
    } 
} 

Answer 3

Zamówienie struny według pierwszego znaku, a następnie długość (najmniejszego do największego), a następnie zastosować dostosowania do KMP znaleźć w this question o złączenie nakładających sznurki.

Answer 4

Interesujący problem. Potrzebujesz pewnego rodzaju cofnięcia. Na przykład, jeśli masz:

ABC, BCD, DBC 

Łącząc DBC z wynikami BCD w:

ABC, DBCD 

który nie jest rozwiązywalne. Ale łącząc ABC z wynikami BCD w:

ABCD, DBC

które mogą być łączone w celu:

ABCDBC. 

Answer 5

Jeśli kod Open Source jest dopuszczalne, to powinien sprawdzić genomu odniesienia w Stanford STAMP Zestaw testów porównawczych: dokładnie to, czego szukasz. Począwszy od wiązki łańcuchów ("genów"), szuka najkrótszego ciągu, który zawiera wszystkie geny. Jeśli na przykład masz ATGC i GCAA, znajdziesz ATGCAA. Nie ma nic na temat algorytmu, który ogranicza go do alfabetu 4-znakowego, więc to powinno być w stanie Ci pomóc.