8. Подмножество a[i..i+M] содержит М+1 строку. Поскольку массив отсортирован, мы можем быстро определить количество общих символов этих М+1 строк, вызвав comlen для первой и последней строки:
comlen(а[1 ] . а[i+М])
На сайте книги приведена программа, реализующая этот алгоритм.
9. Считайте первую строку в массив с, найдите ее конец и допишите после нее завершающий символ \0. Затем считайте следующую строку и завершите ее. Проведите сортировку, как и в предыдущих задачах. При сканировании массива используйте исключающее ИЛИ для того, чтобы гарантировать, что ровно одна строка начинается до границы раздела.
14. Приведенная ниже функция хэширует последовательность из к слов, заканчивающихся символами \0.
unsigned int hash(char *) unsigned int n = 0 i nt n
for (n - k. n >0, p++) h = MULT * n + *p if (*p == 0) n-
return h % NHASH
Программа на сайте книги вызывает эту функцию хэширования вместо двоичного поиска в алгоритме порождения марковского текста, что в среднем уменьшает время ее работы с 0(n\ogn) до О(п). Элементы хэш-таблицы представляют собой списки, размер которых (в 32-разрядпых словах) совпадает с количеством слов в исходном тексте.
Опубликовал vovan666
April 17 2013 00:07:18 ·
0 Комментариев ·
2596 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
