Реферат: Пусть все символы в образце различны. Сравнить по быстродействию простейший алгоритм и алгоритм Рабина-Карпа

Строки

Пусть все символы в образце различны. Сравнить по быстродействию простейший алгоритм и алгоритм Рабина-Карпа. Предложить модификацию простейшего алгоритма, увеличивающую его быстродействие.

Пусть алфавит содержит d символов, и пусть текст и образец - случайные строки длины n и m соответственно. Показать, что математическое ожидание числа сравнений символов, проводимых простейшим алгоритмом при выполнении сравнения строк не превышает 2(n-m+1).

Пусть в образце наряду с символами алфавита  может встречаться символ *, означающий любую подстроку (в том числе и пустую). Разработать алгоритм для поиска такого образца в исходном тексте.

Пусть алфавит содержит d символов, и пусть текст и образец - случайные строки длины n и m соответственно. Подсчитать среднее число холостых срабатываний алгоритма Рабина-Карпа.

Пусть алфавит содержит d символов. Обобщить алгоритма Рабина-Карпа на случай поиска одной из k подстрок.

Обобщить алгоритма Рабина-Карпа на случай поиска квадрата размером m x m в матрице размером n x n.

Сравнить по быстродействию алгоритм Кнута-Морриса- Пратта и алгоритм Рабина-Карпа при поиске в тексте образца, все символы которого различны.

Сравнить по быстродействию алгоритм Кнута-Морриса- Пратта и алгоритм Рабина-Карпа при поиске в тексте одного из k образцов.

Разработать алгоритм для нахождения всех вхождений образца P в текст Т по префикс-функции строки РТ.

Сравнить по быстродействию алгоритм Кнута-Морриса- Пратта и алгоритм Бойера-Мура при поиске в тексте образца, все символы которого различны.

Сравнить по быстродействию алгоритм Бойера-Мура и алгоритм Рабина-Карпа при поиске в тексте образца, все символы которого различны.

Сравнить по быстродействию алгоритм Кнута-Морриса- Пратта и алгоритм Бойера-Мура при поиске в тексте одного из k образцов.

Сравнить по быстродействию алгоритм Бойера-Мура и алгоритм Рабина-Карпа при поиске в тексте одного из k образцов.

Модифицировать простейший алгоритм поиска для нахождения в тексте строки -строки, состоящей из i повторений подстроки y.

Модифицировать алгоритм Кнута-Морриса- Пратта для нахождения в тексте строки -строки, состоящей из i повторений подстроки y.

Модифицировать алгоритм Рабина-Карпа для нахождения в тексте строки -строки, состоящей из i повторений подстроки y.

Модифицировать алгоритм Бойера-Мура для нахождения в тексте строки -строки, состоящей из i повторений подстроки y.

Пусть алфавит содержит d символов. Обобщить алгоритма Рабина-Карпа на случай поиска одной из 2 подстрок, имеющих общий фрагмент .

Пусть алфавит содержит d символов. Обобщить алгоритма Бойера-Мура на случай поиска одной из 2 подстрок, имеющих общий фрагмент .

Пусть алфавит содержит d символов. Обобщить алгоритма Кнута-Морриса- Пратта на случай поиска одной из 2 подстрок, имеющих общий фрагмент .

Пусть алфавит содержит d символов. Обобщить простейший алгоритм на случай поиска одной из 2 подстрок, имеющих общий фрагмент .

Обобщить алгоритм Бойера-Мура на случай поиска одной из 2 подстрок, одна из которых является суффиксом другой.

Обобщить алгоритм Рабина-Карпа на случай поиска одной из 2 подстрок, одна из которых является суффиксом другой.




Обобщить алгоритм Кнута-Морриса- Пратта на случай поиска одной из 2 подстрок, одна из которых является суффиксом другой.




Обобщить алгоритм Бойера-Мура на случай поиска одной из 2 подстрок, одна из которых является префиксом другой.




Обобщить алгоритм Рабина-Карпа на случай поиска одной из 2 подстрок, одна из которых является префиксом другой.




Обобщить алгоритм Кнута-Морриса- Пратта на случай поиска одной из 2 подстрок, одна из которых является префиксом другой.