Міністерство освіти і науки Російської Федерації
ФГБОУ ВПО В«Саратовський державний університет ім. Н.Г. Чернишевського В»
Кафедра математичної кібернетики та комп'ютерних наук
Курсова робота
Пошук підрядка в рядку
Саратов, 2011
Введення
Пошук інформації - одне з основних використань комп'ютера, і швидкий пошук точно заданої підрядка в рядку є однією з самих найпростіших завдань пошуку інформації. Однак це завдання є надзвичайно важливою. Дана функція вбудована в різні текстові редактори і бази даних, що істотно прискорює процес пошуку інформації та редагування (заміну) фрагментів. p align="justify"> В даний час функції пошуку підрядка в рядку інкапсульовані в багато високорівневі мови програмування. Але варто пам'ятати, що стандартні функції далеко не найоптимальніші та ефективні, і якщо основним завданням програми є знаходження підрядка в рядку, то необхідно знати принципи організації функцій пошуку. Також не потрібно забувати, що область застосування функцій пошуку не обмежується одними текстовими редакторами та базами даних. Алгоритми пошуку використовуються різними пошуковими роботами при індексації сторінок, і від швидкості знаходження необхідних ключових слів у тексті html залежить актуальність інформації. Спам-фільтр поштових сервісів також займається пошуком в тексті листів певних фраз, наприклад: В«Мільйон за годинуВ», В«Голосуй за Іванова!В». Та навіть фільтр нецензурних слів і виразів в MMORPG (massively multiplayer online role-playing game - багатокористувацька рольова онлайн-гра) є прикладом застосування даної задачі. Все це говорить про актуальність проблеми пошуку підрядка в рядку. p align="justify"> Мета курсової роботи: вивчити і провести порівняльний аналіз основних алгоритмів пошуку підрядка в рядку. Розглянути кілька практичних завдань на дану тему. p align="justify"> Завдання курсової роботи: привести основні визначення по темі пошуку підрядка в рядку, розглянути застосування різних алгоритмів на практиці, створити програму, що реалізовує деякі з цих алгоритмів.
1. Алгоритми пошуку підрядка в рядку
.1 Основні визначення та поняття
Визначення [1]. Рядок (слово) - це послідовність знаків, званих літерами, з деякого кінцевого безлічі, званого алфавітом. p align="justify"> Визначення [1]. Довжина рядка - кількість знаків у рядку. p align="justify"> Слова позначаються буквами латинського алфавіту, наприклад послідовність - слово довгою , де -ая буква слова. Будемо позна...
