Algorytm Apostolico – Giancarlo
W informatyce Apostolico – Giancarlo jest odmianą przeszukiwania ciągów Boyera – Moore'a , którego podstawowym zastosowaniem jest wyszukiwanie wystąpień wzorca tekście poprzez wyrównanie do określonego indeksu i , czy dopasowanie występuje w tym indeksie. jest przesuwany względem zgodnie z zasadami algorytmu Boyera-Moore'a, a proces powtarza się aż do . Zastosowanie reguł przesunięcia Boyera-Moore'a często powoduje całkowite pominięcie dużych fragmentów tekstu.
Jeśli chodzi o operację zmiany, Apostolico – Giancarlo jest dokładnie równoważny pod względem funkcjonalności z Boyer – Moore. Użyteczność Apostolico-Giancarlo polega na przyspieszeniu operacji sprawdzania dopasowania w dowolnym indeksie. W przypadku Boyera-Moore'a znalezienie wystąpienia w wymaga wyraźnego dopasowania wszystkich z { W przypadku niektórych wzorców i tekstów jest to bardzo nieefektywne - prostym przykładem jest sytuacja, gdy zarówno wzór, jak i tekst składają się z tego samego powtarzającego się znaku, w którym to przypadku Boyer – Moore działa w , gdzie O ( n m ) { \ to długość w znakach . Apostolico – Giancarlo to, rejestrując liczbę znaków dopasowanych w wyrównaniach tabeli, która jest łączona z danymi zebranymi podczas wstępnego przetwarzania, aby uniknąć zbędnego sprawdzania dla sekwencji znaków, o których wiadomo, że pasują. Można to postrzegać jako uogólnienie reguły Galila .
- Apostolico, Alberto; Giancarlo, Raffaele (1986). „Ponowna wizyta w strategiach przeszukiwania ciągów Boyer – Moore – Galil” . SIAM Journal o informatyce . 15 : 98–105. doi : 10.1137/0215007 .
- Crochemore, Maxime; Lecroq, Thierry (1997). „Ścisłe granice złożoności algorytmu Apostolico-Giancarlo” (PDF) . Listy dotyczące przetwarzania informacji . 63 (4): 195–203. doi : 10.1016/S0020-0190(97)00107-5 .
- Crochemore, M.; Rytter, W. (1994). Algorytmy tekstowe . Oxford University Press .
- Gusfield, D. (1997). Algorytmy na ciągach, drzewach i sekwencjach: informatyka i biologia obliczeniowa . Wydawnictwo Uniwersytetu Cambridge . ISBN 0-521-58519-8 .
- Lecroq, T. (1992). Recherches de Mots (praca doktorska). Uniwersytet w Orleanie .
- Lecroq, Thierry (1995). „Eksperymentalne wyniki algorytmów dopasowywania ciągów”. Oprogramowanie: praktyka i doświadczenie . 25 (7): 727–765. doi : 10.1002/spe.4380250703 . S2CID 15253073 .