Blogo simbolio taisyklė
Blogo simbolio taisyklė (arba Boyer-Moore algoritmas) – teksto paieškos ilgoje eilutėje algoritmas. Algoritmas ieško palyginti trumpos eilutės kitoje (paprastai daug ilgesnėje) iš anksto nežinomoje eilutėje. Tuo jis skiriasi nuo priesagų medžius naudojančių algoritmų, kuriems ilgąja eilutę reikia žinoti iš anksto – medžiui sukurti. Klasikinis Boyer-Moore algoritmas remiasi trimis paprastomis taisyklėmis: Trumpoji eilutė (kurios ieškoma) prieš paiešką analizuojama, sudarant lentelę. Kiekvienai eilutės padėčiai įsimenama, kiek toli į kairę nuo jos eilutėje yra kiekviena abėcėlei priklausanti raidė. Specialiu kodu pažymimi atvejai, kai tokios raidės į kairę nuo šios padėties ieškomoje eilutėje nėra. Nors pati paieška vyksta iš kairės į dešinę, simboliai lyginami iš dešines į kairę („atbulai“). Nustačius kad duotojoje padėtyje ieškomos eilutės nėra, pirmajame žingsnyje atliktos analizės rezultai panaudojami nustatyti, kur pradėti ieškoti iš naujo: a) Jei nesutampančio ilgosios eilutės simbolio kairiojoje trumposios eilutės dalyje nėra, lyginimo rėmels patraukiamas tiek, kad šis simbolis į jį nebepatektų. b) Jei šis simbolis trumpojoje eilutėje labiau į kairę yra, rėmelis patraukiamas tiek, kad šieji du simboliai atsidurtų vienas virš kito.