SHPORA.net :: PDA | |
|
Main FAQ гуманитарные науки естественные науки математические науки технические науки Sõnealgoritmid: Boyer-Moore'i algoritm. Boyer-Moore'i algoritm Ka Boyer-Moore'i algoritm pühendub "paremale hüppamisele" tekstis. Sobitamine toimub paremalt vasakule, prefiksfunktsiooni asemel arvutatakse sufiksfunktsioon ning lisaks veel sümboli nn. viimase esinemise funktsioon (iga sümboli viimase esinemise positsioon otsisõnes, mitteesinemisel null). Valitakse maksimaalne erinevate hüppevõimaluste vahel. Praktikas saavutatakse oluliselt pikemad hüpped, ideaaljuhul taandub keerukus O(n/m)-ni, halvim keerukus on O(mn). Sama algoritm pseudokoodis Täiustatud variant: |