Knut-Morris-Prat algoritmi
Ключевые слова:
Knut-Morris-Pratt algoritmi, qidiruv algoritmlari, substring qidiruvi, prefiks-funksiyasi, algoritm murakkabligi, C# dasturlash, matnni qayta ishlashАннотация
Mazkur maqolada matn ichida namunaviy qatorni (substring) qidirishda samarali ishlovchi Knut-Morris-Pratt (KMP) algoritmi tahlil qilinadi. Ushbu algoritm klassik qidiruv algoritmlaridan farqli ravishda takroriy taqqoslashlarni kamaytiradi va O(n)
vaqt murakkabligiga ega. KMP algoritmi matn tahlili, bioinformatika, qidiruv tizimlari va plagiat aniqlash kabi sohalarda keng qo‘llaniladi. Maqolada algoritmning ishlash prinsipi, prefiks-funksiyani qurish bosqichlari va C# tilida dasturlashdagi amaliy
namunalar keltirilgan.
Библиографические ссылки
1.
Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast Pattern Matching in
Strings. SIAM Journal on Computing.
2.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction
to Algorithms (3rd ed.). MIT Press.
3.
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge
University Press.4.
Aho, A. V., & Ullman, J. D. (1995). Foundations of Computer Science. W. H.
Freeman.
5.
Brassard, G., & Bratley, P. (1996). Fundamentals of Algorithmics. Prentice-Hall.
6.
Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison
Wesley.
7.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
8.
Levitin, A. (2012). Introduction to the Design and Analysis of Algorithms.
Pearson.
9.
Skiena, S. (2008). The Algorithm Design Manual. Springer.
10.
Press.
11.
Gokhale, S. S. (2017). Data Structures and Algorithms. University Science
GeeksforGeeks.
Rosetta
(n.d.).
KMP Algorithm for Pattern Searching.
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
12.
Code.
(n.d.).
https://rosettacode.org/wiki/KMP_string_search
13.
Microsoft
Docs.
14.
(n.d.).
String
KMP
Searching
string
Algorithms
search.
in
C#.
Horowitz, E., Sahni, S., & Rajasekaran, S. (2007). Fundamentals of Computer
Algorithms. University Press.
15.
Baeza-Yates, R., & Ribeiro-Neto, B. (2011). Modern Information Retrieval: The
Concepts and Technology behind Search. Addison-Wesley.
