| Book of tasks on programming. Old version
|
| 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
Одной из распространенных задач является поиск подстроки в строке. Результатом поиска должно быть число, показывающее, с какой позиции в строке начинается искомая подстрока. Рассмотрим следующие алгоритмы поиска. Прямой поиск. Проходим по всем символам строки, за исключением нескольких последних, на длину искомой подстроки, и проверяем, не с этого ли символа начинается искомая подстрока. Алгоритм Кнута, Мориса и Пратта (КМП). Данный алгоритм является улучшением прямого поиска. После очередного сравнения, следующее сравнение начинается не со следующего символа строки, а происходит перепрыгивание через несколько символов, исходя из уже проанализированной информации. Алгоритм Боуера и Мура. Данный алгоритм основан на той же идее, что и КМП, только поиск идет посредством перебора символов, начиная с конца искомой подстроки.
|