Book of tasks on programming. Old version

 

 by Aliaksandr N. Prykhodzka

 

text, insert, applet, implementation, library, interface, path, навучальны зборнiк па праграмаванню, in, чайник, параметр, xslt, servlet, самообучение
 

for valuable work you must have JavaScript (allow active content)

Pascal. Pa.24. Algorithms. Strings

Одной из распространенных задач является поиск подстроки в строке. Результатом поиска должно быть число, показывающее, с какой позиции в строке начинается искомая подстрока. Рассмотрим следующие алгоритмы поиска. Прямой поиск. Проходим по всем символам строки, за исключением нескольких последних, на длину искомой подстроки, и проверяем, не с этого ли символа начинается искомая подстрока. Алгоритм Кнута, Мориса и Пратта (КМП). Данный алгоритм является улучшением прямого поиска. После очередного сравнения, следующее сравнение начинается не со следующего символа строки, а происходит перепрыгивание через несколько символов, исходя из уже проанализированной информации. Алгоритм Боуера и Мура. Данный алгоритм основан на той же идее, что и КМП, только поиск идет посредством перебора символов, начиная с конца искомой подстроки.

 

©   Aliaksandr Prykhodzka    1993 - 2007