Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Точный поиск подстроки в строке /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Обозначения и определения. - Программирование от RIN.RU
Обозначения и определения.

Термины не обязательно запоминать: будут в алгоритме - вернетесь.


Искомый образец - строка x = x [ 0 ... m - 1 ]; его длина m.
Текст - строка y = y [ 0 ... n - 1 ]; его длина n.


Алфавит ( множество символов, из которых составлены текст и образец ) - S, в нем s символов.
Слово u - префикс cлова w, если существует слово v : w = uv.
Слово v - суффикс cлова w, если существует слово u : w = uv.
Слово z - подстрока слова w, если существуют u и v : w = uzv.
Слово u - период слова w, если w - префикс слова uk для целого k. Наименьший период мы далее и будем называть периодом и обозначать per(w).
Cлово w длины l - периодичное, если длина per(w) <= l/2, в противном случае оно непериодичное.
Слово называется фундаментальным, если оно не может быть записано в виде степени другого слова, то есть не существует z : w = zl.
Cлово z - граница слова w, если существуют u и w : w = uz = zv, z - одновременно префикс и суффикс w.
Обращение слова w длины l обозначается wR - зеркальный образ w; wR = w[ l-1 ]w[ l-2 ] ... w[1]w[0].


В программах будут использованы следующие функции и константы:


константа ASIZE - размер алфавита,
константа WORD - размер компьютерного слова в битах, обычно 16
константа XSIZE - размер образца,
функция ERROR сообщает об ошибке,
функции MIN / MAX - минимум / максимум,
функция OUTPUT возвращает позицию начала совпадения относительно начала текста.


В остальном же все, я надеюсь, следует стандарту Aнси - Си.



 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь