Слова — основа любого документа. Множество важных задач можно решить поиском слов. Однако иногда приходится искать фразы наподобие «поиск подстроки» или «неявные структуры данных» в длинных строках (в собственных документах, файлах справки, web-страницах или вообще во всей сети).
Как бы вы стали искать в большом тексте «фразу из нескольких слов»? Если вы никогда не видели этого текста, вам пришлось бы начать с начала и просмотреть его целиком. В большинстве учебников по теории алгоритмов описываются различные подходы к решению задачи «поиска подстроки».
Предположим, что у вас есть возможность заранее подготовить текст перед тем, как осуществлять поиск. Можно сделать хэш-таблицу или дерево поиска для индексации всех слов документа и хранить в ней список всех вхождений всех слов документа. Такой обратный индекс позволит программе быстро найти в тексте любое слово. Фразы можно разделять на отдельные слова, но это сложно реализовать и такая программа может оказаться медленной. Однако в некоторых поисковых системах в Интернете для индексации web-страниц используется именно этот подход.
Теперь мы возьмем мощную структуру данных и используем ее в небольшой задаче. Нужно найти самую длинную повторяющуюся подстроку символов в большом текстовом файле. Например, самая длинная повторяющаяся подстрока в фразе «Ask not what your country can do for you, but what you can do for your country» — «can do for you», тогда как подстрока «your country» стоит на втором месте. Как бы вы написали программу, решающую эту задачу?
Здесь уместно вспомнить задачу об анаграммах из раздела 2.4 главы 2. Если входная строка хранится в массиве с [0..п-1], мы можем начать с последовательного сравнения всех возможных пар подстрок, написав что-нибудь подобное:
maxlen = -1
for i = [0, n) for j = (i , n)
if (thislen = comlen(&c[i]. &c[j])) > maxlen maxien = thislen maxi = i maxj = j
Функция comlen (листинг 15.7) возвращает длину одинаковой части двух строк (начиная с первых символов), передаваемых ей в качестве аргументов.
Листинг 15.7. Функция comlen — вычисление длины общей части двух строк
int comlen(char *р, char *q)
i = О
while *p && (*p++ == *q+ + ) i ++ return i
Поскольку этот алгоритм проверяет все возможные пары подстрок, он является квадратичным. Мы смогли бы ускорить его с помощью хэш-таблицы для поиска слов в фразах, но вместо этого мы попробуем новый подход.
Наша новая программа будет обрабатывать не более MAXN символов, хранящихся в массиве с:
#define MAXN 5000000 char с[MAXN], *а[MAXN],
Опубликовал vovan666
April 17 2013 00:04:43 ·
0 Комментариев ·
3114 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
