Jak osiągnąć "dopasowanie podłańcuchów" w czasie O (n)?

Question

mam zadanie, które wymaga czytania ogromny plik przypadkowych wejść, na przykład:

Adana 
Izmir Adnan Menderes Apt 
Addis Ababa 
Aden 
ADIYAMAN 
ALDAN 
Amman Marka Intl Airport 
Adak Island 
Adelaide Airport 
ANURADHAPURA 
Kodiak Apt 
DALLAS/ADDISON 
Ardabil 
ANDREWS AFB 
etc.. 

Gdybym podać szukaną frazę, program ma znaleźć linie którym wystąpi podciąg. Na przykład, jeśli wyszukiwanym hasłem jest "uradha", program ma pokazać ANURADHAPURA. Jeśli wyszukiwanym hasłem jest "lotnisko", program ma pokazać: Amman Marka Intl Airport, Adelaide Airport

Cytat ze specyfikacji przypisania: "Musisz zaprogramować tę aplikację, biorąc pod uwagę efektywność, tak jak w przypadku dużych ilości danych i przetwarzania. "

Mogę łatwo osiągnąć tę funkcję za pomocą pętli, ale wydajność będzie O (n). Myślałem o użyciu trie, ale wygląda na to, że działa tylko wtedy, gdy podciąg zaczyna się od indeksu 0.

Zastanawiam się, jakie są rozwiązania, które dają lepszą wydajność niż O (n)?

Answer 1

Możesz rzucić okiem na Boyer-Moore string search algorithm lub Knuth-Morris-Pratt string search algorithm. Mają dobrą asymptotyczną wydajność, ale nie znam algorytmu, który nie wymagałby przynajmniej odczytu raz (prawie wszystkich) zarówno ciągu wejściowego, jak i wyjściowego, a zatem miałby lepszą wydajność niż O (n) (gdzie n jest wielkością danych wejściowych).

Answer 2

Here's jeden z O (n) jako najgorszy przypadek złożoność czasu.

Nawiasem mówiąc, należy utworzyć zakładkę ten link: http://www-igm.univ-mlv.fr/~lecroq/string/

Answer 3

Mój gut mówi, że jesteś na dobrej myśli ścieżek trie a może chcesz, aby zbadać tę sekcję strony trie na Wikipedia że linki do Suffix Tree dla kilku innych pomysłów. O (n) pomysły niestety.

Answer 4

To tekst wejściowy zawartość niemal statyczne (lub wartości nie są dodawane tak często, a wartości są dodawane do końca źródła sygnału wejściowego), ale przeszukiwanie jest często można wypróbować następujące (prawdopodobnie taki sam jak trie)

1) będziesz przeczytać cały tekst (a także aktualizować następnie dodaje nowy element) i przygotować indeksy tabel (mapa symbolu współrzędnych (wiersz lub wiersz z pozycji) Jeśli występuje mecz)

'aa' - 1, 15, 27... 
'as' - 1, 15, 17... 
'ba' - 2, 3, 15... 
... 

2) Pierwsza współrzędna wyszukiwania w tabeli indeksów według pierwszych 2 symboli

3) Następnie kontynuuj wyszukiwanie w tekście wejściowym za pomocą współrzędnych

Answer 5

Boyer-Moore i kilka algorytmów, które wykorzystują warianty w niektórych swoich pomysłach, mogą osiągnąć "O (n/m)" (gdzie n jest długością stogu siana i m to długość igły) najlepsze działanie na niektórych igłach, ale zależy to od kryteriów braku powtórzenia na igle, których nie można spełnić dla arbitralnie dużych m (np. ponieważ m jest znacznie większy niż rozmiar zestawu znaków), czyniąc nawet najlepsze przypadki czymś bardziej podobnym do O (n/256), a zatem O (n). Wciąż w rzeczywistych aplikacjach, gdzie m jest zwykle mały, a igły nie mają patologicznego punktu widzenia, BM i jego kuzyni potrafią działać wyjątkowo dobrze.

Osobiście polecam algorytm "Dwukierunkowy" (z rozszerzeniami podobnymi do BM używanymi w implementacji glibc), ponieważ ma zagwarantowane granice O (n) i stałą przestrzeń roboczą.