20.500.12556/DKUM-22898 Iskanje niza v besedilu String matching Besedilo B in niz S sta zaporedji znakov iz abecede ∑. Pri problemu iskanja niza v besedilu želimo poiskati vse ponovitve niza S v besedilu B. V ta namen so v prvem poglavju diplomskega dela predstavljene teoretične osnove. Opisan je princip snovanja in ob tem predstavljen postopek ocenjevanja časovne in prostorske zahtevnosti algoritmov. Drugo poglavje je namenjeno teoretičnim osnovam, ki se pojavljajo pri problemu iskanja niza v besedilu. Predstavljena je definicija, nato so opisane lastnosti in zakonitosti, ki se pojavljajo tekom iskanja nizov v besedilu. Naslednja poglavja so namenjena predstavitvi treh algoritmov, ki se uporabljajo pri nalogah iskanja niza v besedilu. Opisane so njihove lastnosti, njihovo delovanje pa je predstavljeno z različnimi grafičnimi prikazi ter psevdokodo. Za vsakega izmed njih je prav tako predstavljena ocena časovne zahtevnosti. The text B and string S are sequences of characters from the alphabet ∑. The problem of string matching is to find all occurences of the string S in the text B. For this purpose the first chapter presents the theoretical basics. The design principle is described, while the evaluation of algorithm's time and space complexity is presented. The second chapter is devoted to theoretical foundations that are encoutered through the process of string matching. Definition and description of characteristics and principles that may arise during the string matching process is described. The following chapters are intended to present three algorithms that are used in string matching tasks. Described are their properties while their actions are presented with various graphical presentations and pseudocode. For each of them the evaluation of time complexity was also made. niz besedilo iskanje ujemanje algoritem naivni Rabin-Karp končni avtomat časovna zahtevnost prostorska zahtevnost pattern string searching matching algorithm naive brute-force Rabin-Karp finite automata time complexity space complexity true true false [S. Pukšič] Slovenski jezik Angleški jezik Diplomsko delo 2012-05-08 15:34:31 2012-05-23 11:51:25 2022-04-14 12:11:28 2023-12-30 03:30:50 2012 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 19144456 URN:SI:UM:DK:IXVJXVIO UNI_Puksic_Sergej_2012.pdf UNI_Puksic_Sergej_2012.pdf 1 1AE87023378CBD4028963A0FB679E908 2366efa238e6a6f5d65cb09d004cbe429b5eae3f9821bdfa5c11fb241095613c 98e88f82-7c06-11eb-bb7a-00155d0001ca 20.500.12556/dkum/a7ab253e-668e-4498-aacc-22fef8cc4585 https://dk.um.si/Dokument.php?lang=slv&id=29814 Fakulteta za naravoslovje in matematiko 0 0 0