Time-Efficient String Matching Algorithms and the Brute-Force Method

LUMBUROVSKA, LINA (author), Robič, Borut (mentor)

One of the most researched areas of computer science is the string matching problem. In everyday life, people read, write, and encounter character strings all the time. Very often they want to find substrings (e.g. words) that match parts of the original text and have higher probability of matching. Finding a new efficient algorithm for the String Matching Problem involves a tremendous number of testing, just to slightly improve on the existing algorithms. In this, the algorithm based on the Brute-Force Method is of considerable help, as many current algorithms are founded on it. My bachelor thesis explores different algorithms for the String Matching Problem and comes to a conclusion that each such algorithm has advantages and disadvantages, and is suitable for solving a particular version of the String Matching Problem and type of situations. Nevertheless, the most used algorithm in practice is the Knuth-Morris-Pratt algorithm.

• Language: English
• Keywords: string, matching, algorithm
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2018
• PID: 20.500.12556/RUL-103414
• Publication date in RUL: 17.09.2018

Secondary language

• Language: Slovenian
• Title: Časovno učinkoviti algoritmi ujemanja nizov in metoda grobe sile

Abstract

Eno izmed najbolj raziskanih področij na področju računalništva je problem ujemanja nizov. V vsakodnevnem življenjem ljudje ves čas berejo, pišejo, srečujejo nize in pogosto želijo najti nekaj podnizov ali besed, ki se ujemajo z izvirnim besedilom in imajo večjo verjetnost ujemanja. Razvoj mnogih algoritmov za problem ujemanja nizov zahteva ogromno preizkušanja, če želimo le malenkostno izboljšati kak obstoječi algoritem. Pri tem nam je velikokrat v pomoč algoritem, ki deluje po metodi grobe sile, saj na njem temelji veliko novejših algoritmov. V svoji diplomski nalogi sem raziskala različne vrste algoritmov za problem ujemanja nizov in prišla do zaključka, da ima vsak tak algoritem svoje prednosti in slabosti in je uporaben le za reševanje posebnih oblik tega problema in pripadajočih situacij. Vendar se v praksi izkaže, da je najpogosteje uporabljen tako imenovani Knuth-Morris-Prattov algoritem.

• Keywords: niz, ujemanje, algoritem