Tìm các xâu độc đáo nhỏ nhất cho mỗi chuỗi trong một mảng

Question

(Tôi viết những dòng này trong bối cảnh JavaScript, nhưng sẽ chấp nhận một câu trả lời đúng thuật toán bằng ngôn ngữ nào)

Làm thế nào để bạn tìm thấy chuỗi con ngắn nhất của mỗi phần tử trong một chuỗi các chuỗi trong đó chuỗi con KHÔNG được chứa trong bất kỳ phần tử nào khác, bỏ qua trường hợp?

Giả sử tôi có một mảng đầu vào như:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 

Đầu ra phải được cái gì đó như:

var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"]; 

Đối với mục đích của tôi, bạn có thể giả định rằng không có yếu tố sẽ được chứa hoàn toàn trong vòng một yếu tố khác.

Suy nghĩ của tôi:
Dường như người ta có thể có sức mạnh vũ phu này, dọc theo dòng:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch; 
// For each name 
for (nameInd = 0; nameInd < names.length; nameInd++) 
{ 
    var name = names[nameInd]; 
    // For each possible substring length 
    windowLoop: 
    for (windowSize = 1; windowSize <= name.length; windowSize++) 
    { 
     // For each starting index of a substring 
     for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++) 
     { 
      substr = name.substring(substrInd,substrInd+windowSize).toLowerCase(); 
      foundMatch = false; 
      // For each other name 
      for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++) 
      { 
       if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1) 
       { 
        foundMatch = true; 
        break; 
       } 
      } 

      if (!foundMatch) 
      { 
       // This substr works! 
       uniqueNames[nameInd] = substr; 
       break windowLoop; 
      } 
     } 
    } 
} 

Nhưng tôi có thể tưởng tượng có một giải pháp thanh lịch hơn khi sử dụng cố gắng/cây tiền tố, mảng hậu tố, hoặc một cái gì đó thú vị như thế.

Edit: Tôi tin rằng đây là hình thức câu trả lời được lựa chọn sẽ mất lập trình trong JavaScript:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 
var uniqueNames = [], permutations = {}, permutation, nameInd, windowSize, substrInd, substr; 

// For each name 
for (nameInd = 0; nameInd < names.length; nameInd++) 
{ 
    var name = names[nameInd]; 
    // For each possible substring length 
    windowLoop: 
    for (windowSize = 1; windowSize <= name.length; windowSize++) 
    { 
     // For each starting index of a substring 
     for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++) 
     { 
      substr = name.substring(substrInd,substrInd+windowSize).toLowerCase(); 
      permutations[substr] = (typeof permutations[substr] === "undefined")?nameInd:-1; 
     } 
    } 
} 

for (substr in permutations) 
{ 
    permutation = permutations[substr]; 
    if (permutation !== -1 && ((typeof uniqueNames[permutation] === "string" && substr.length < uniqueNames[permutation].length) || typeof uniqueNames[permutation] === "undefined")) 
    { 
     uniqueNames[permutation] = substr; 
    } 
} 

Answer 1

Say N là số chuỗi và L là chiều dài tối đa của chuỗi. Bạn đang thực hiện tối đa N*L*L*N lần lặp.

Tôi chỉ có thể cải thiện nó một chút bằng cách giao dịch một lần lặp cho bộ nhớ bổ sung. Đối với mỗi chiều dài chuỗi con có thể (L lặp),

• liệt kê tất cả các chuỗi con đó chiều dài trong mỗi tên (N*L), và lưu trữ nó trong số với chỉ số tên vào một Hashtable (1). Nếu đã có chỉ mục cho chuỗi con này, bạn biết nó sẽ không hoạt động, sau đó bạn thay thế chỉ mục bằng một số giá trị đặc biệt, như -1.

• đi Hashtable, nhặt chuỗi con mà chỉ số không phải là -1 - đó là câu trả lời cho các chỉ số tương ứng của họ, nhưng chỉ sử dụng chúng nếu đó là tên chưa có một câu trả lời ngắn hơn từ một sự lặp lại trước

Việc sử dụng bộ nhớ có thể giảm đáng kể bằng cách lưu tham chiếu trở lại vào chuỗi hiện có thay vì sao chép dữ liệu.

Answer 2

Sự cố này có thể được giải quyết trong O (N * L * L * L) độ phức tạp. Cách tiếp cận sẽ được sử dụng cố gắng hậu tố. Mỗi nút của trie cũng sẽ lưu trữ số đếm tiền tố sẽ tham chiếu đến số lần chuỗi con được tạo trong khi đi ngang qua nút đó từ gốc đã xuất hiện trong tất cả các hậu tố được chèn cho đến bây giờ.

Chúng tôi sẽ xây dựng N + 1 cố gắng.Trie đầu tiên sẽ là toàn cục và chúng ta sẽ chèn tất cả các hậu tố của tất cả các chuỗi N vào nó. N lần thử tiếp theo sẽ là địa phương cho mỗi chuỗi N chứa hậu tố tương ứng.

Bước xử lý tiền xử lý thử này sẽ được thực hiện trong O (N * L * L).

Bây giờ khi cố gắng đã được xây dựng, đối với mỗi chuỗi, chúng ta có thể bắt đầu quering số lần một chuỗi con (bắt đầu từ chiều dài tối thiểu) đã xảy ra trong Trie toàn cầu và Trie tương ứng với chuỗi đó. Nếu nó giống nhau trong cả hai thì nó ngụ ý rằng nó không được bao gồm trong bất kỳ chuỗi nào khác ngoại trừ chính nó. Điều này có thể đạt được trong O (N * L * L * L). Độ phức tạp có thể được giải thích là N cho mỗi chuỗi, L * L để xem xét từng chuỗi con và L để thực hiện truy vấn trong trie.

Answer 3

Nếu bạn xây dựng cây hậu tố tổng quát, bạn chỉ cần tìm điểm cạn nhất mà tại đó một phần của mỗi nhánh chuỗi ra khỏi các phần của các chuỗi khác và đưa nhãn đến điểm nhánh đó cộng với một điểm "phân biệt" tính cách. Các kicker là có phải là một nhân vật phụ (nó có thể được phân nhánh chỉ ở metacharacter mắc kẹt vào cuối mỗi chuỗi), và các nhánh-off điểm có thể không dẫn đến một lá, nó có thể dẫn đến một cây con với tất cả các lá từ cùng một chuỗi (vì vậy các nút bên trong phải được xem xét).

Đối với mỗi chuỗi S tìm nút cạn nhất (theo chiều rộng nhãn phụ) N chỉ chứa các lá từ S và nhãn cạnh có chứa ít nhất một ký tự. Nhãn đường dẫn từ gốc đến phụ huynh của N, cộng với một ký tự từ nhãn cạnh dẫn đến N, là số thập phân ngắn nhất của S không tìm thấy trong các chuỗi khác.

Tôi tin rằng việc ghi nhãn các nút chỉ chứa các lá từ một chuỗi có thể được thực hiện trong quá trình xây dựng hoặc bằng cách quét O (N) của GST; thì đó là một vấn đề đơn giản để quét cây cuối cùng và giữ mức tối thiểu cho mỗi chuỗi. Vì vậy, đó là tất cả O (N).

(chỉnh sửa - Tôi không thể trả lời bình luận nào)

Để làm rõ, mỗi hậu tố trong một cây hậu tố có một nút mà nó chi nhánh khỏi hậu tố khác; mục tiêu ở đây là tìm/hậu tố cho mỗi chuỗi mà nhánh rẽ từ hậu tố của tất cả các chuỗi khác ở độ sâu tối thiểu, được đo bằng nhãn đường dẫn đến nút đó. Tất cả những gì chúng ta cần là một nhân vật phụ sau thời điểm đó để có một chuỗi con không xuất hiện trong bất kỳ chuỗi nào khác.

Ví dụ:

Strings: abbc, abc

Sử dụng thuật toán Ukonnen, sau khi chuỗi đầu tiên chúng ta có một cây hậu tố của chỉ là hậu tố từ chuỗi đó; Tôi sẽ đánh giá chúng là với [1] ở đây:

abbc[1] 
b 
bc[1] 
c[1] 
c[1] 

Tiếp theo chúng ta chèn chuỗi 2 của hậu tố:

ab 
    bc[1] 
    c[2] 
b 
bc[1] 
c 
    [1] 
    [2] 
c 
[1] 
[2] 

Bây giờ chúng tôi muốn tìm ra chuỗi ngắn nhất dẫn đến một chi nhánh với chỉ [1] dưới nó; chúng ta có thể làm điều đó bằng cách quét tất cả các [1] 's và nhìn vào cha mẹ của họ ngay lập tức, mà tôi sẽ liệt kê ở đây bởi nhãn đường, cộng với một nhân vật (mà tôi sẽ sử dụng dưới đây):

abbc: abb 
bbc: bb 
bc: bc[1] 
c: c[1] 

Lưu ý rằng tôi đã bao gồm [1] vì đó là metacharacter phân biệt các hậu tố giống hệt nhau của [1] và [2]. Điều này rất tiện lợi khi xác định các chất nền lặp lại trong nhiều chuỗi, nhưng nó không hữu ích cho vấn đề của chúng ta, vì nếu chúng ta xóa [1] chúng ta kết thúc bằng một chuỗi xảy ra trong [2], tức là nó không phải là một ứng cử viên.

Hiện tại, không có nhãn nào ở bên phải xuất hiện trong bất kỳ chuỗi nào khác, vì vậy chúng tôi chọn nhãn ngắn nhất không bao gồm siêu ký tự, đó là bb.

Tương tự, chuỗi thứ hai có những ứng cử viên:

abc: abc 
bc: bc[2] 
c: c[2] 

Chỉ có một không có một metacharater ở cuối, vì vậy chúng tôi phải đi với abc.

Điểm cuối cùng của tôi là tìm kiếm tối thiểu trên mỗi chuỗi này không nhất thiết phải xảy ra một lần; GST có thể được quét một lần để gắn nhãn các nút có chứa các lá từ một chuỗi ([1], [2], .. [n]) hoặc "hỗn hợp", và sau đó các chuỗi không chia sẻ tối thiểu cho mỗi chuỗi (tôi sẽ gọi những "infixes phân biệt") có thể được tính trong một pass là tốt.