Sugestia algorytmu ciągów, aby znaleźć wszystkie wspólne przedrostki listy łańcuchów znaków

Question

Jaki algorytm zaproponowałbyś, aby znaleźć najdłuższe wspólne przedrostki listy łańcuchów?

Może mam ciągi takie jak:

Call Mike and schedule meeting. 
Call Lisa 
Call Adam and ask for quote. 
Implement new class for iPhone project 
Implement new class for Rails controller 
Buy groceries 

Chcę dowiedzieć się następujące przedrostki:

"Call " 
"Implement new class " 

będę przy użyciu Objective C, a więc gotowe rozwiązanie byłoby kakao plus (choć nie musi).

Answer 1

To zależy od tego, co chcesz wziąć pod uwagę przedrostek.

Przypuszczam, że ogólną odpowiedzią jest utworzenie Trie (prawdopodobnie drzewo sufiksowe), które przechowuje wszystkie ciągi w n-ar drzewo. Zobacz http://en.wikipedia.org/wiki/Trie

zależności od kryteriów „przedrostek” (powiedzmy n znaków) można wybrać wszystkie węzły rangi n, które mają więcej niż jedno dzieci.

Będziesz mieć listę powtarzających się prefiksów.

Answer 2

Można wstawić wszystkie ciągi znaków do trie (drzewo prefiksów). Następnie przechodź przez trie z katalogu głównego, aż znajdziesz węzeł z więcej niż jednym dzieckiem (lub po prostu przestań wstawiać łańcuchy, gdy będziesz musiał dołączyć drugie dziecko do węzła).

Answer 3

Edit: dla sklarowanego pytanie:

1. posortować ciągi
2. znaleźć najdłuższy wspólny przedrostek każdej sąsiedniej pary
3. sortować i DeDupe wspólne prefiksy, a następnie usunąć dowolny to ścisła prefiksem inne.

W rzeczywistości krok (3) wymaga jedynie usunięcia wszystkich duplikatów/przedrostków innego, które można wykonać przy użyciu trie lub innego rodzaju sortowania. W rzeczywistości może być tak, że cała sprawa może być wykonana szybciej z odpowiednio opisanym trie - jeśli w każdym węźle znajduje się "licznik", to szukasz właśnie węzłów o liczbie 2+, które nie mają dzieci z liczba 2+.

Ale sortowanie jest wbudowane, a po posortowaniu można wykryć przedrostki, patrząc na sąsiednie przedmioty, więc to prawdopodobnie mniej wysiłku.

[odpowiedź oryginalny:

Tylko operacja jednorazowa, znajdź najdłuższy wspólny przedrostek między wszystkimi strun?

Prawdopodobnie zrobiłbym to pod względem długości prefiksu. Pseudo-kod, przy założeniu, ciągi nul zakończone:

prefixlen = strlen(first_string); 
foreach string in the list { 
    for (i = 0; i < prefixlen; ++i) { 
     if (string[i] != first_string[i]) { 
      prefixlen = i; 
      break; 
     } 
    } 
    if (prefixlen == 0) break; 
} 

common_prefix = substring(firststring, 0, prefixlen); 

]

Answer 4

1. wprowadzeniu wszystkich łańcuchów w strukturze danych Trie.
2. DFS z katalogu głównego, aby znaleźć pierwszy węzeł, z którego wychodzi więcej niż jedna krawędź.
3. ścieżka od katalogu głównego do węzła obliczonego w kroku 2 daje najdłuższy wspólny przedrostek dla wszystkich zestawów łańcuchów.