Thuật toán ốp lát chuỗi

Question

Tôi đang tìm một thuật toán hiệu quả để làm ốp lát. Về cơ bản, bạn được cung cấp một danh sách các chuỗi, nói BCD, CDE, ABC, A, và kết quả lát gạch chuỗi nên ABCDE, vì BCD thẳng hàng với CDE năng suất BCDE, đó là sau đó căn chỉnh với ABC cho kết quả cuối cùng là ABCDE.

Hiện tại, tôi đang sử dụng thuật toán hơi ngây thơ, hoạt động như sau. Bắt đầu với một cặp ngẫu nhiên của chuỗi, nói BCD và CDE, tôi sử dụng sau đây (trong Java):

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 

Mặc dù công trình này, nó không phải là rất hiệu quả, vì nó lặp qua các nhân vật tương tự hơn và hơn nữa.

Vì vậy, không ai biết thuật toán tốt hơn (hiệu quả hơn) (hiệu quả hơn) để thực hiện điều này? Vấn đề này tương tự như một vấn đề liên kết chuỗi DNA, vì vậy mọi lời khuyên từ một người nào đó trong lĩnh vực này (và những người khác, tất nhiên) đều được chào đón rất nhiều. Ngoài ra, xin lưu ý rằng tôi không tìm kiếm một liên kết , nhưng một lát là ốp lát, bởi vì tôi yêu cầu chồng chéo đầy đủ một trong các chuỗi so với chuỗi kia.

Tôi hiện đang tìm kiếm sự thích ứng của Rabin-Karp algorithm, để cải thiện độ phức tạp tiệm cận của thuật toán, nhưng tôi muốn nghe một số lời khuyên trước khi giải quyết thêm bất kỳ vấn đề nào.

Xin cảm ơn trước.

---

Đối với trường hợp có sự mơ hồ - ví dụ, {ABC, CBA} mà có thể dẫn đến ABCBA hoặc CBABC -, bất kỳ ốp lát có thể được trả lại. Tuy nhiên, tình trạng này hiếm khi xảy ra, bởi vì tôi đang tiling từ, ví dụ {This is, is me} => {This is me}, được điều khiển để thuật toán nói trên hoạt động.

tương tự câu hỏi: Efficient Algorithm for String Concatenation with Overlap

Answer 1

Điều đầu tiên cần đặt ra là nếu bạn muốn tìm việc cày ải đất của {CDB, CDA}? Không có tilling đơn lẻ.

Answer 2

Tôi nghĩ rằng điều này sẽ làm việc cho việc ốp lát hai chuỗi và hiệu quả hơn so với triển khai hiện tại của bạn bằng cách sử dụng chuỗi con và chứa. Khái niệm tôi lặp qua các ký tự trong chuỗi 'trái' và so sánh chúng với một ký tự trong chuỗi 'phải'. Nếu hai nhân vật khớp nhau, tôi chuyển sang ký tự tiếp theo trong chuỗi bên phải. Tùy thuộc vào chuỗi nào kết thúc lần đầu tiên đến, và nếu các ký tự so sánh cuối cùng phù hợp hay không, một trong các trường hợp ốp lát có thể được xác định.

Tôi chưa nghĩ đến bất kỳ điều gì để cải thiện độ phức tạp của thời gian lát hơn hai chuỗi. Là một lưu ý nhỏ cho nhiều chuỗi, thuật toán này dưới đây có thể dễ dàng mở rộng để kiểm tra ốp lát của một chuỗi 'trái' đơn có nhiều chuỗi 'phải' cùng một lúc, điều này có thể ngăn chặn chuỗi lặp thêm một chút nếu bạn đang cố gắng tìm hiểu xem có nên làm ("ABC", "BCX", "XYZ") hay ("ABC", "XYZ", BCX ") bằng cách chỉ thử tất cả các khả năng.

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

thứ tự các dây bằng ký tự đầu tiên, sau đó chiều dài (nhỏ nhất đến lớn nhất), và sau đó áp dụng thích nghi với KMP tìm thấy trong this question về concatenating dây chồng chéo.

Answer 4

Sự cố thú vị. Bạn cần một số loại backtracking. Ví dụ, nếu bạn có:

ABC, BCD, DBC 

Kết hợp DBC với kết quả BCD trong:

ABC, DBCD 

Mà không phải là giải quyết được. Nhưng kết hợp ABC với kết quả BCD trong:

ABCD, DBC

Mà có thể được kết hợp để:

ABCDBC. 

Answer 5

Nếu mã nguồn mở là chấp nhận được, sau đó bạn nên kiểm tra bộ gen tiêu chuẩn ở Stanford STAMP tiêu chuẩn bộ: nó hiện khá nhiều chính xác những gì bạn đang tìm kiếm. Bắt đầu với một chuỗi các chuỗi ("gen"), nó tìm kiếm chuỗi ngắn nhất kết hợp tất cả các gen. Vì vậy, ví dụ nếu bạn có ATGC và GCAA, nó sẽ tìm thấy ATGCAA. Không có gì về thuật toán giới hạn nó thành một bảng chữ cái 4 ký tự, do đó, điều này sẽ có thể giúp bạn.