Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms
URI (for links/citations):https://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 ...
Bykova, Valentina V.; Быкова, Валентина В. (Сибирский федеральный университет. Siberian Federal University., 2011-04)We give a brief overview of results and problems of parameterized algorithmics as the new direction of computational complexity theory. We offer a new indicator of computational complexity for parameterized algorithm ...
Тяпкин, Валерий Николаевич; Дмитриев, Дмитрий Дмитриевич; Карцан, Игорь Николаевич; Ефремова, Светлана Владимировна (2017-07)The following paper discusses a conducted synthesis and assessment of the effectiveness of control algorithms for null formation in the radiation pattern of a flat phased antenna array according to two coordinates; the ...
Тяпкин, Валерий Николаевич; Карцан, Игорь Николаевич; Дмитриев, Дмитрий Дмитриевич; Ефремова, Светлана Владимировна (2017-10)The following paper discusses a conducted synthesis and assessment of the effectiveness of control algorithms for null formation in the radiation pattern of a flat phased antenna array according to two coordinates; the ...