Znajdź najmniejszą unikalny podciąg dla każdej struny w tablicy

Question

(piszę to w kontekście JavaScriptu, ale akceptuje się algorytmicznie poprawną odpowiedź w dowolnym języku)

Jak odnaleźć najkrótszy podłańcuch każdego elementu w tablicy ciągów, gdzie podciąg NIE jest zawarty w żadnym z pozostałych elementów, ignorując przypadek?

Załóżmy, że mam tablicę wejściowych, takich jak:

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

Wyjście powinno być coś takiego:

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

Dla moich celów, można bezpiecznie założyć, że żaden element nie zostanie całkowicie zawarty w kolejny element.

myśli moje
Wydaje się, że ktoś mógłby prawdopodobnie brutalnej siły tej, wzdłuż linii:

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; 
      } 
     } 
    } 
} 

Ale muszę sobie wyobrazić, istnieje bardziej eleganckie rozwiązanie za pomocą prób/drzew przedrostek, tablice sufiksu lub coś tak interesującego.

Edit: Wierzę, że to jest forma wybrana odpowiedź zajęłoby programowo w 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 wiele strun i L jest maksymalna długość łańcucha. Wykonujesz do iteracji N*L*L*N.

Mogę tylko trochę poprawić, handlując jedną iteracją dla dodatkowej pamięci. Dla każdej możliwej długości podciągu (L iteracji)

• wyliczyć wszystkie podciągi tej długości w każdej nazwy (N*L) i przechowywać je między indeksem imienia do hashtable (1). Jeśli istnieje już indeks dla tego podciągu, wiesz, że nie zadziała, wtedy zastąpisz indeks specjalną wartością, np. -1.

• chodzić hashtable, zbierając podciągi, dla których indeks nie jest -1 - że są odpowiedzi do odpowiadających im indeksów, ale tylko z nich korzystać jeśli nazwy nie masz jeszcze krótszy odpowiedzi z poprzedniej iteracji

Zużycie pamięci można znacznie zmniejszyć, zapisując odniesienie do istniejącego ciągu zamiast kopiowania podciągów.

Answer 2

Ten problem można rozwiązać w złożoności O (N * L * L * L). Podejście będzie przy użyciu prób sufiksów. Każdy węzeł trie będzie również zapisywać liczbę prefiksów, która będzie odnosić się do liczby razy, gdy podłańcuch utworzony podczas przechodzenia do tego węzła z korzenia pojawił się we wszystkich przyrostkach wstawionych do tej pory.

Będziemy budować próby N + 1.Pierwszy trie będzie globalny i będziemy wstawiać do niego wszystkie przyrostki wszystkich N. Następne próby będą lokalne dla każdego z ciągów znaków zawierających odpowiednie sufiksy.

Ten etap wstępnego przygotowania zostanie wykonany w O (N * L * L).

Teraz, po skonstruowaniu prób, dla każdego ciągu możemy rozpocząć wyliczanie ile razy wystąpił podłańcuch (począwszy od minimalnej długości) w globalnym trie i trie odpowiadającym temu ciągowi. Jeśli jest taka sama w obu przypadkach, oznacza to, że nie jest zawarty w żadnych innych łańcuchach oprócz samego siebie. Można to osiągnąć w O (N * L * L * L). Złożoność można wytłumaczyć jako N dla każdego ciągu, L * L dla uwzględnienia każdego podciągu i L dla wykonania zapytania w trie.

Answer 3

Jeśli tworzysz uogólnione drzewo sufiksów, po prostu znajdź najciemniejszy punkt, w którym infiks każdego łańcucha oddzieli się od wgłębień innych łańcuchów, i przenieś etykietę do tego rozgałęzienia plus jeden "wyróżniający". postać. Kicker jest taki, że musi istnieć taka dodatkowa postać (może rozgałęziać się tylko na metaznakach zatrzymanych na końcu każdego ciągu), a punkt rozgałęzienia może nie prowadzić do liścia, może prowadzić do poddrzewa z liśćmi wszystkie z tego samego ciągu (więc należy wziąć pod uwagę wewnętrzne węzły).

Dla każdego ciągu S znajdź najłagodniejszy (wg głębokości nadrzędnej) węzeł N, który zawiera tylko liście z S, i którego etykieta krawędzi zawiera co najmniej jeden znak. Etykieta ścieżki od korzenia do rodzica N plus jeden znak od etykiety krawędzi prowadzącej do N jest najkrótszym infiksem S, którego nie znaleziono w innych ciągach.

Uważam, że etykietowanie węzłów, które zawierają tylko liście z jednego ciągu, może być wykonane podczas budowy lub ze skanowania O (N) GST; wtedy łatwo skanować ostatnie drzewo i utrzymywać minimalne wartości dla każdego ciągu. Więc wszystko to O (N).

(edit - Nie mogę odpowiadać na komentarze jeszcze)

Aby wyjaśnić, każdy sufiks w drzewo przyrostek ma węzeł gdzie odgałęzia się od innych przyrostków; celem jest znalezienie sufiksu/a dla każdego łańcucha, który rozgałęzia się od sufiksów wszystkich pozostałych łańcuchów na minimalnej głębokości, jak zmierzono etykietą ścieżki do tego węzła. Potrzebujemy tylko jednego dodatkowego znaku po tym punkcie, aby mieć podciąg, który nie pojawia się w żadnym innym ciągu.

Przykład:

Struny: abbc, abc

użyciu algorytmu Ukonnen jest po pierwszym ciągiem mamy drzewo przyrostek zaledwie przyrostków z tego łańcucha; Będę oznaczyć je [1] tutaj:

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

Następnie wstawić ciąg 2 za przyrostków:

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

Teraz chcemy znaleźć najkrótszą ciąg, który prowadzi do oddziału z tylko [1] jest pod nim; Można to zrobić poprzez skanowanie wszystkich [1] 's, a patrząc na ich bezpośrednich rodziców, które będę tu wymieniać przez etykietę ścieżki, plus jeden znak (który będę używał poniżej):

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

pamiętać, że 've included [1], ponieważ jest metaznakiem odróżniającym identyczne sufiksy z [1] i [2]. Jest to przydatne przy identyfikacji podciągów, które powtarzają się w wielu ciągach, ale nie jest to użyteczne dla naszego problemu, ponieważ jeśli usuniemy [1], otrzymamy również ciąg, który występuje w [2], tzn. Nie jest kandydatem.

Teraz żadna z etykiet po prawej nie występuje w żadnym innym ciągu, więc wybieramy najkrótszy bez metaznaków, czyli bb.

Podobnie, drugi ciąg ma tych kandydatów:

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

Tylko jeden nie posiada metaznaku na końcu, więc musimy iść z ABC.

Moja ostatnia uwaga jest taka, że ​​to ustalenie minimalne dla ciągu nie musi następować pojedynczo; GST może zostać zeskanowany jeden raz, aby oznaczyć węzły jako zawierające liście z jednego ciągu znaków ([1], [2], .. [n]) lub "mieszane", a następnie ciągi niewystępujące w ciągach (ja nazwać te "rozróżniające infiksy") można obliczyć również w jednym przejściu.