Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: International Scientific Conference Reshetnev Readings 2015; Красноярск, Россия; Красноярск, Россия
Год издания: 2016
Идентификатор DOI: 10.1088/1757-899X/122/1/012034
Ключевые слова: Algorithms, Pattern matching, Basic principles, Boyer-Moore, Boyer-Moore algorithms, Combined algorithms, Running speed, Searching speed, String-searching, String searching algorithms
Аннотация: 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. © Published under licence by IOP Publishing Ltd.
Журнал: IOP Conference Series: Materials Science and Engineering
Выпуск журнала: Vol. 122, Is. 1