V textových algoritmech je vyhledávací algoritmus podřetězce typem vyhledávacího algoritmu , jehož cílem je najít řetězec znaků (vzor P ) uvnitř jiného řetězce (text T ).
Existuje mnoho textových formátů, ve kterých je třeba hledat, a ve výsledku se u všech algoritmů pravděpodobně objeví velké variace v závislosti na poskytnutém T- textu .
Například velikost textu se může lišit od jednoho řádku po zřetězení tisíců knih. Kódování textu může mít také dramatický vliv na výkonnost algoritmu. Zejména abecedy typu DNA, ASCII nebo Unicode mohou automaticky vyloučit použití konkrétního algoritmu.
Cílem je provést porovnání počátečního řetězce a hledaného řetězce po jednotlivých znacích. Znaky počátečního řetězce jsou skenovány, pokud se liší od prvního znaku nalezeného řetězce. Jakmile najdeme identický znak, projdeme následujícími znaky, dokud se shodují. Pokud se znak liší, když jsme nedosáhli konce hledaného řetězce, pokračujeme v hledání prvního identického znaku, počínaje od dalšího znaku v počátečním řetězci. Pokud se všechny znaky shodují, vrátíme pozici prvního znaku řetězce nalezeného v počátečním řetězci. Nakonec, pokud se v počátečním řetězci neobjeví žádný výskyt hledaného řetězce, musí jej algoritmus signalizovat, například vrácením záporné hodnoty.
U malých T textů je tento algoritmus efektivní. Nicméně, složitost algoritmu je t Vstup (| T | * | P |) je rychle předjet algoritmů, které používají specifika P nebo T před provedením vyhledávání, která se nazývá předzpracování.
Hlavní článek - Knuth-Morris-Prattův algoritmus
Hlavní článek - Boyer-Mooreův algoritmus
Hlavní článek - algoritmus Boyer-Moore-Horspool
Hlavní článek - Raitaův algoritmus
Hlavní článek - algoritmus Baeza-Yates-Gonnet
Hlavní článek - Algoritmus Z
Algoritmy v této části provádějí těžké předzpracování na T textu nebo více vstupních P_i vzorů , aby bylo možné porovnat více P_i s částí textu pouze jednou. Některé klasické příklady jsou detekce plagiátorství nebo porovnání podezřelého souboru s fragmenty viru.
Hlavní článek - Rabin-Karpův algoritmus .
Hlavní článek - Aho-Corasickův algoritmus .
Výše uvedené algoritmy jsou akademické. V praxi jsou vysoce přizpůsobené potřebám v této oblasti.
Některé knihovny kombinují více algoritmů, aby zůstaly v nejlepším možném případě rozlišení. Například řetězec liblib / fastsearch v Pythonu používá hrubou sílu pro P délky 1 a kombinaci filtrů Boyer-Moore-Horspool a Sunday a Bloom k nahrazení skákací tabulky.
Některé programy jako grep nabízejí nesčetné množství optimalizací a obětují svůj nejhorší případ pro nejlepší případ, sázejí na skutečnost, že P a T mají nízkou pravděpodobnost vzniku patologického případu.
A konečně, moderní procesory nabízejí obzvláště efektivní instrukční sady SIMD , jako je SSE . Některé implementace libc strstr používají tyto příkazy k urychlení hledání.