Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms
URI (for links/citations):http://elib.sfu-kras.ru/handle/2311/27966
Царев, Р. Ю.
Черниговский, А. С.
Царева, Е. А.
Брезицкая, В. В.
Никифоров, А. Ю.
Смирнов, Н. А.
Институт космических и информационных технологий
Кафедра технологических машин и оборудования
Journal Name:IOP Conference Series: Materials Science and Engineering
Journal Quartile in Scopus:Q4
Bibliographic Citation:Царев, Р. Ю. Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms [Текст] / Р. Ю. Царев, А. С. Черниговский, Е. А. Царева, В. В. Брезицкая, А. Ю. Никифоров, Н. А. Смирнов // IOP Conference Series: Materials Science and Engineering. — 2016. — Т. 122 (№ 1). — .
The string searching task can be classified as a classic information processing task. Users either encounter the solution of this task while working with text processors or browsers, employing standard built-in tools, or this task is solved unseen by the users, while they are working with various computer programmes. Nowadays there are many algorithms for solving the string searching problem. The main criterion of these algorithms' effectiveness is searching speed. The larger the shift of the pattern relative to the string in case of pattern and string characters' mismatch is, the higher is the algorithm running speed. This article offers a combined algorithm, which has been developed on the basis of well-known Knuth-Morris-Pratt and Boyer-Moore string searching algorithms. These algorithms are based on two different basic principles of pattern matching. Knuth-Morris-Pratt algorithm is based upon forward pattern matching and Boyer-Moore is based upon backward pattern matching. Having united these two algorithms, the combined algorithm allows acquiring the larger shift in case of pattern and string characters' mismatch. The article provides an example, which illustrates the results of Boyer-Moore and Knuth-Morris- Pratt algorithms and combined algorithm's work and shows advantage of the latter in solving string searching problem.
Metadata:Show full item record
Showing items related by title, author, creator and subject.
Kazakovtsev, Lev; Antamoshkin, Alexander (2016-10)In this paper, we investigate application of various options of algorithms with greedy agglomerative heuristic procedure for object clustering problems in continuous space in combination with various ...
Recursive algorithm for exhaustive search of possible multiversion software realizations with the choice of the optimal versions set Царев, Р. Ю.; Грузенкин, Д. В.; Гришина, Г. В. (2018-04)N-version software is used all over the world as one of the approaches that can provide with the high level of reliability and software fault tolerance. The application of redundant module versions of software allows to ...
Краснов, Тимур Валериевич; Бондаренко, Валерий Николаевич; Гарифуллин, Вадим Фанисович; Феоктистов, Денис Сергеевич; Богатырёв, Евгений Владимирович (2018-11)An algorithm is proposed for parallel algorithm of delay search for a quasi-periodic noise-like signal with a minimum frequency modulation. It is shown that with a slight loss in noise immunity (0.9dB), the considered ...
Transformation of the Subject in the Act of the Reverse birth: Analysis of the Search of the Lost Mother (based on A. Platonov’s Texts) Glushenkova, Olga A.; Глушенкова, О.А. (Сибирский федеральный университет. Siberian Federal University, 2016-05)The article is dedicated to the ontological analysis of A. Platonov’s texts. The classical theme of orphancy, raised by the writer, is analyzed through the definitions of J. Kristeva about searching of the lost motherly. ...
Medvedev, Igor A.; Медведев, И.А. (Сибирский федеральный университет. Siberian Federal University., 2016-01)The article notes the relevance and incompleteness of the study by the lawyers and criminalists of the issues of urgent searches. It examines the state of the current legislation on the search procedures, including urgent ...