Технологии поиска документальной информации в INTERNET

  • Добавили06.08.2003
  • Размер42,19 Kб
  • Скачали3976

часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием. Более точно, можно записать неравенство li1 l i - число итераций на i-м шаге1 или число итераций на i-м шаге li-li11 Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций. Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m.

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

Решение. Применяем алгоритм КМП к слову АВ. При этом вычисление значений l1 l n проводим для слова X длины n и запоминаем эти значения.

Дальше мы помним только значение li для текущего i - кроме него и кроме таблицы l1 ln, нам для вычислений ничего не нужно. На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем.

Написать соответствующий алгоритм проверяющий, является ли слово Xx1 xn подсловом слова Yy1 ym Решение. Сначала вычисляем таблицу l1 lnкак раньше. Затем пишем такую программу j0 len0 len - длина максимального качала слова X, одновременно являющегося концом слова y1 jj while len n and j m do begin while xlen1 уj1 and len 0 do begin начало не подходит, применяем к нему функцию l len llen end нашли подходящее или убедились в отсутствии if xlen1yj1 do begin x1 xlen - самое длинное подходящее начало lenlen1 end else begin подходящих нет len0 end jj1 end если lenn, слово X встретилось иначе мы дошли до конца слова .

Скачать
Контрольная Коммуникации и связь 13.08.2008

Все об интернете

1 1. История сети Интернет 2 2. Что такое Интернет 3-4 3. Применения Интернета 4-7 3.1 Электронная почта 4 3.2 Передача файлов 5 3.3 Удаленный доступ 5 3.4 Как движутся данные – среда передачи 6 3.5 Коммутируемые линии 6 3.6 Арендуемые линии 6 3.7 Микроволновая

Реферат Компьютерные сети 24.06.2000

Глобальная сеть INTERNET

Всплеск интереса к глобальной информационной сети Internet наблюдается сейчас повсеместно В сложившихся условиях потребность в информации о сети Internet становится особенно острой. В настоящее время по Internet распространяется множество документов,

Курсовая Информатика 11.06.2010

гипертекстовая технология

… …3 1 Гипертекст… 5 1.1 Понятие гипертекста…5 1.2 История развития гипертекста…7 1.3 Простая технология построения гипертекста….10 2 Гипертекстовая технология… 12 2.1 Общие понятия… 12 2.2 Применения гипертекстовых технологий… 15 2.3 Гипертекстовые Web-документы….

Курсовая Журналистика, издательское дело и СМИ 23.12.2009

Источники информации (Общая характеристика)

Информация- это творчество, а не ремесло, когда по Старой форме штампуют несколько изделий… А. Рубинов. На этапе разработки замысла журналистского произведения необходимо, прежде всего, определиться с объектом изучения. В качестве данного объекта изучения

5ballov.qip.ru рекомендует:

  • Выбор ВУЗа

    С приходом лета начался период, когда выпускники школ выбирают куда пойдут учиться дальше. Конечно, это совсем не легкий выбор, но помочь в выборе может рейтинг вузов на нашем сайте. Также в этом разделе представлена вся нужная для абитуриентов информация.

  • Как сдать ЕГЭ

    Прежде, чем идти в выбранный вуз с документами, нужно сначала получить аттестат, который выдается после сдачи экзаменов. А подготовиться к ним можно в нашем разделе ЕГЭ. Там также представлены варианты за прошлые года.

  • Подготовка к ГИА

    Для девятиклассников не менее важно окончание учебного года. Их также ждет государственная итоговая аттестация. Подготовиться к ней можно на нашем сайте в разделе ГИА. Главное помнить: самоподготовка - это путь к успешной сдаче.

Облако тегов