Аналіз завдання
 Скачать 17.4 Kb.
|
|
Аналіз завдання Пошук підрядка в рядку - одна з найпростіших задач пошуку інформації. Застосовується у вигляді вбудованої функції в текстових редакторах, СУБД, пошукових машинах, мовах програмування і т. д.. Алгоритми пошуку рядка — важливий клас рядкових алгоритмів, що намагаються знайти місце де один або декілька текстових рядків входять у довший рядок або текст. Ті, кому доводиться часто працювати з текстовими редакторами, знають ціну функції знаходження потрібних слів в тексті, істотно полегшуючої редагування документів і пошук потрібної інформації. Дійсно, сучасні програми обробки тексту привчили нас до такої зручної можливості, як пошук і заміна фрагментів, і якщо ви розробляєте подібну програму, користувач має право очікувати, що ви надасте в його розпорядження відповідні команди. Область застосування функції пошуку не обмежується одними лише текстовими редакторами. Слід зазначити використання алгоритмів пошуку при індексації сторінок пошуковим роботом, де актуальність інформації безпосередньо залежить від швидкості знаходження ключових слів у тексті html-сторінки. Робота найпростішого спам-фільтра, полягає в знаходженні в тексті таких фраз, як «Мільйон за годину» або «Розкрутка сайту». Все вищесказане свідчить про актуальність проблеми, зачепленої роботою. Поставимо задачу пошуку підрядка в рядку. Нехай у нас є рядок, що складається з певної кількості символів. Нам потрібно перевірити, чи входить інший заданий рядок в даний текст, і якщо входить, то починаючи з якого символу тексту. Для розв’язання поставленої задачі використаємо алгоритм пошуку підрядка в рядку Боуера-Мура. Алгоритм, розроблений двома вченими - Боуером (Robert S. Boyer) і Муром (Strother Moore), вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку. |