Algoritam za pretragu nizova

Из Википедије, слободне енциклопедије

U informatici, algoritmi za pretragu nizova (algoritmi za sravnivanje niski) su važna klasa algoritama niski koji pokušavaju da nađu mesto gde se jedan ili nekoliko niski (ili obrazaca) nalaze unutar veće niske ili teksta. Oni mogu da pretražuju tekst formiran od normalnog alfabeta, binarnog alfabeta, ili DNK alfabeta (A, C, G, T).

Način kodiranja niza može da ograniči opseg primenljivih algoritama za pretragu. Na primer ako se koristi kodiranje promenljive širine mnogi algoritmi postaju veoma spori, te su specifične adaptacije algoritama neophodne.

Literatura[уреди]

  • R. S. Boyer and J. S. Moore, A fast string searching algorithm, Carom. ACM 20, (10), 262–272(1977).
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 32: String Matching, pp.906–932.

Spoljašnje veze[уреди]