1

Федеральное агентство связи

ФГОБУ ВПО «СибГУТИ»

Кафедра вычислительных систем

Курсовая работа по дисциплинам

«Программирование», «Языки программирования»

семестр 2

2013/2014 учебный год

Преподаватели:

Доцент Кафедры ВС, к.т.н. Поляков Артём Юрьевич Старший преподаватель Кафедры ВС Перышкова Евгения Николаевна

ТРЕБОВАНИЯ К КУРСОВЫМ РАБОТАМ

Требования к курсовым работам 1. Все программы реализуются на языке Си.

2. Необходима проверка всех входных данных на корректность. В случае ошибки должно выдаваться сообщение, поясняющее суть ошибки для пользователя. Далее программа должна завершаться.

3. Для сдачи курсовой работы необходимо подготовить отчет, включающий приведенные ниже пункты:

3.1. Титульный лист, оформленный согласно шаблону, размещенному на WEB-странице предмета. В поле название пишется название раздела к которому относится вариант;

3.2. Задание — содержит текст задания;

3.3. Анализ задачи, приводится развернутый анализ задачи, описываются методы и алгоритмы ее решения (особенно важные фрагменты представляются блок-схемами или псевдокодом). Если используются известные алгоритмы (кодирования, архивации, поиска) для них также необходимо привести описание и демонстрацию работы на примере;

3.4. Тестовые данные: максимально полный набор тестовых данных (в том числе некорректных) демонстрирующий работу разработанного ПО. Данный раздел должен присутствовать обязательно;

3.5. Листинг программы, раздел содержит исходные коды разработанного ПО. При оформлении можно использовать 8 размер шрифта и размещать текст программы в 2 колонки. Текст программы должен быть отформатирован.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

1. Получение информации через аргументы командной строки В большинстве заданий входные данные или имена файлов, содержащих входные данные, должны передаваться через аргументы командной строки. Эта информация является частью «окружения» программы. Все аргументы командной строки передаются в виде строк и доступны через формальные параметры функции main. Прототип функции main в программе, использующей аргументы командной строки, выглядит следующим образом:

int main(int argc, char **argv) где argc – количество строк-аргументов, а argv – массив указателей на сами строки-аргументы.

Рассмотрим следующий пример:

$./prog first_arg “second arg” third arg На вход программе будет передана следующая информация:

Обратите внимание, что в командной строке пробел является разделителем, поэтому строка third arg разбивается на два аргумента. Если требуется, чтобы входной аргумент содержал пробелы – строку необходимо заключать в кавычки, например, "second arg".

Первым элементом argv (argv[0]) всегда является имя исполняемого файла программы.

Обработка входных аргументов может производиться напрямую через взаимодействие с массивом argv, однако существует ряд функций, позволяющих упростить процесс разбора входных параметров. Это функции getopt и getopt_long. Более подробную информацию об использовании этих функций можно получить в справочном руководстве ОС GNU/Linux – "man 3 getopt", данная страница доступна на русском языке на сайте проекта opennet.ru:

http://www.opennet.ru/man.shtml?topic=getopt&category=3&russian=0.

Также примеры использования указанных функций есть на сайте FirstSteps:

http://www.firststeps.ru/linux/r.php?10.

2. Взаимодействие с файловой системой Для выполнения некоторых заданий потребуются инструменты, позволяющие получать информацию о содержимом директорий в файловой системе. В ОС GNU/Linux для решения этой задачи предусмотрены следующие функции:

#include #include DIR *opendir(const char *name);

int closedir(DIR *dirp);

#include struct dirent *readdir(DIR *dirp);

Функция opendir выполняет "открытие" директории для чтения, на вход ей передается строка, содержащая путь к директории, возвращаемым значением является указатель на структуру DIR, которая используется для дальнейших действий с открытой директорией.

Функция readdir выполняет последовательный проход по содержимому открытой директории.

При каждом ее вызове она возвращает указатель на структуру типа struct dirent, элементы которой приведены ниже:

struct dirent { ino_t d_ino; /* i node number */ off_t d_off; /* offset to the next dirent */ unsigned short d_reclen; /* length of this record */ unsigned char d_type; /* type of file; not supported by all file system types */ char d_name[256]; /* filename */ };

Для выполнения заданий курсовой работы интерес представляют поля d_name и d_type. Первое содержит имя файла или директории, второе – позволяет определить тип элемента файловой системы, это поле представляет из себя целое число, которое устанавливается функцией readdir в одно из допустимых значений, которые представлены константами, определенными в файле dirent.h:

DT_BLK Блочное устройство (например, файл жесткого диска) DT_CHR Символьное устройство (клавиатура, мышь) DT_DIR Директория DT_FIFO Именованные программные каналы (для взаимодействия DT_SOCK Unix – сокет (для взаимодействия между программами).

DT_UNKNOWN Неизвестный тип файла.

В рамках курсовой работы предусмотрена обработка только директорий (DT_DIR) и регулярных файлов (DT_REG), другие типы файлов должны игнорироваться.

Функция closedir закрывает директорию, после ее вызова функция readdir не должна использоваться с данной структурой типа DIR.

Дополнительную информацию об объектах файловой системы можно получить, используя функцию stat (самостоятельное изучение).

ЗАДАНИЯ НА КУРСОВУЮ РАБОТУ

РАЗДЕЛ 1. ОБРАБОТКА ПОСЛЕДОВАТЕЛЬНОЙ ИНФОРМАЦИИ

В рамках данного раздела рассматриваются различные задачи обработки последовательностей.

Задания данного раздела считаются упрощенными, однако для некоторых из них предложен усложненный вариант, который предусматривает оценку «отлично».

ВАРИАНТ 1.1-1.3 РАЗРАБОТКА БИБЛИОТЕКИ СОРТИРОВОК Задание Реализовать динамическую библиотеку сортировок. Алгоритмы сортировок выбираются в соответствии с вариантом задания. Проанализировать эффективность алгоритмов сортировки. Разработать демонстрационную программу, использующую созданную библиотеку.

Критерии оценки Оценка «удовлетворительно»: алгоритмы реализованы в виде простой программы без применения библиотек, данные поступают на вход с клавиатуры. Тесты проведены только на небольших последовательностях, нет анализа и сравнения алгоритмов. Не предусмотрено динамическое выделение памяти под входные данные.

Оценка «хорошо»: работа выполнена в полном соответствии с заданием. Обязательно динамическое выделение памяти под входные данные.

Оценка «отлично»: помимо выполнения условий задания предусмотрена сортировка произвольных данных (по аналогии с функцией qsort библиотеки GNU C Library – GLibC). Обязательно динамическое выделение памяти под входные данные.

Указания к выполнению задания Алгоритмы сортировки необходимо реализовать в подпрограммах. Подпрограммы выносятся в отдельную библиотеку, которая компилируется как динамическая. Информация о создании и испольFirstSteps:

зовании динамических библиотек может быть найдена на ресурсе http://firststeps.ru/linux/general1.html.

Эффективность сортировок оценивать по времени работы алгоритмов. По полученным результатам сформулировать выводы о преимуществах и недостатках каждого алгоритма. В Выводы должны быть обоснованы проводимыми исследованиями зависимостей времени работы алгоритмов от размера как упорядоченных (по возрастанию и по убыванию), так и случайных последовательностей. Необходимо провести исследования дл последовательностей, размером 28 – элементов (с некоторым шагом). Построить графики полученных зависимостей. В случае, если время работы одного из алгоритмов превышает 15 мин., прекратить измерения по данному алгоритму и строить график не на всем интервале.

Сортировка методом пузырька, быстрая сортировка Сортировка вставками, пирамидальная сортировка.

Сортировка Шелла, сортировка слиянием.

ВАРИАНТ 1.4 ПОИСК ПАЛИНДРОМОВ В ТЕКСТЕ

Задание Разработать программу palindrom, выполняющую поиск всех палиндромов в заданном тексте.

Команда palindrom принимает в качестве аргумента командной строки имя файла, содержащего текст на русском языке. Все найденные палиндромы распечатываются на экране.

Критерии оценки Оценка «удовлетворительно»: реализована проверка того, что весь текст входного файла целиком является палиндромом. Динамическое выделение памяти под входные данные не предусмотрено.

Оценка «хорошо»: реализована предварительная обработка текста: из каждого предложения удаляются все знаки препинания. После этого осуществляется проверка каждого предложения на выполнение свойства палиндрома. Обязательно динамическое выделение памяти под входные данные.

Оценка «отлично»: реализована предварительная обработка текста: из текста удаляются все пробелы и знаки препинания так, чтобы получилось одно большое слово. Для поиска подпалиндромов используется динамическое программирование (http://comp-science.narod.ru/WebPage/p6.htm). Обязательно динамическое выделение памяти под входные данные.

Указания к выполнению задания Палиндромом называются слово (потоп, шалаш) или текст (а роза упала на лапу Азора), читающиеся одинаково в обоих направлениях.

ВАРИАНТ 1.5 РАЗРАБОТКА ПРОСТЕЙШЕГО ПЕРЕВОДЧИКА

Задание Разработать программу translate, выполняющую перевод текста с помощью словаря. Команда translate принимает на вход 3 файла. Первый содержит исходный текст, который необходимо перевести. Второй файл имеет вид простейшего словаря, где каждому слову на одном языке соответствует слово на другом. Третий файл необходимо создать и записать в него результат работы переводчика.

Формат исходного текста должен быть сохранен.

Критерии оценки Оценка «удовлетворительно»: не реализована поддержка файла-словаря, словарь задается статически в программе. Динамическое выделение памяти под входные данные не предусмотрено.

Оценка «отлично»: программа реализована в полном соответствии с заданием. Обязательно динамическое выделение памяти под входные данные.

Указания к выполнению задания Рассмотрим работу программы на примере:

$ translate text_rus.txt dictionary.txt text_eng.txt # перевод текста в text_rus с помощью словаря Тигр, жгучий страх.

Ты горишь в ночных лесах.

Чей бессмертный взор, Форматирование текста в файле text_rus.txt сохранено в итоговом файле text_eng.txt, т.е. сохранены все сдвиги и переносы по тексту. Задание не предусматривает поиск однокоренных слов, поэтому замена слова происходит только по полному соответствию.

ВАРИАНТ 1.6 ЧАСТОТНЫЙ АНАЛИЗ ТЕКСТА

Задание Реализовать программу calcFrequency, производящую частотный анализ слов в исходном тексте. На вход программы calcFrequency подается 2 файла. Первый файл содержит текст, который подлежит анализу. Второй файл необходимо создать, и записать все слова, встретившиеся в тексте с указанием частоты появления. Расположить слова в порядке убывания частоты их встречаемости.

Критерии оценки Оценка «удовлетворительно»: реализован подсчет количества символов и слов в тексте.

Динамическое выделение памяти под входные данные не предусмотрено.

Оценка «отлично»: программа реализована в полном соответствии с заданием. Обязательно динамическое выделение памяти под входные данные.

Указания к выполнению задания Рассмотрим работу программы на примере:

$ calcFrequency text1.txt text2.txt Записывать во второй файл только те слова, частота встречаемости которых больше 1. Склонения и однокоренные слова считать разными словами.

РАЗДЕЛ 2. РАЗРАБОТКА ИНСТРУМЕНТОВ КОМАНДНОЙ СТРОКИ ОС GNU/LINUX

В заданиях данного раздела требуется разработать программные утилиты командной строки в соответствии с вариантом задания. Все входные данные передаются через аргументы командной строки (с использованием аргументов функции main). Использование системного вызова system() запрещено, допустимо использовать только системные вызовы ОС GNU\Linux.

ВАРИАНТ 2.1 ИНТЕРПРЕТАТОР СКРИПТОВ

Задание Разработать интерпретатор скриптов (ИС) - sinterp. Команда sinterp принимает в качестве входных данных имя файла, содержащего скрипт.

Доступные операции: =, +, –, >,, 0.

Скрипт может содержать следующие языковые конструкции:

1) ввод/вывод данных (read/print);

2) цикл (while – do – done );

3) ветвление (if – then – else – fi) Критерии оценки Оценка «хорошо»: работа только с целыми числами, использование конструкций вводавывода и циклических конструкций. Вложенность циклических конструкций не предусматривается.

Оценка «отлично»: работа с целыми и вещественными числами (отслеживание корректности использования переменных), должны быть реализованы все предусмотренные конструкции. Должна быть реализована возможность использования вложенных конструкций ветвление и цикл.

Формат доступных конструкций Конструкции ввода-вывода:

read [тип данного:

-i или -f] write [тип данного:

-i или -f] При работе только с целыми числами спецификаторы формата реализовывать не нужно.

done.

Примеры входных данных Вычисление суммы элементов последова- Поиск минимального элемента последовательности

ВАРИАНТ 2.2 КАЛЬКУЛЯТОР КОМАНДНОЙ СТРОКИ

Задание Разработать программу калькулятор cmdcalc, предназначенную для вычисления простейших арифметических выражений с учетом приоритета операций и расстановки скобок. На вход cmdcalc через аргументы командной строки поступает символьная строка, содержащая арифметическое выражение. Требуется проверить корректность входного выражения (правильность расстановки операндов, операций и скобок) и, если выражение корректно, вычислить его значение.

Арифметическое выражение записывается следующим образом: A p B или ( A p B ), где A – левый операнд, B - правый операнд, p – арифметическая операция. A и B – вещественные числа, p = + | - | * | /. Например: ( ( ( (1.1-2) +3) * (2.5*2) ) + 10), (1.1 – 2) +3 * (2.5 * 2) + 10. Пример вызова команды cmdcalc (обратите внимание, что входное выражение необходимо взять в кавычки!):

$ cmdcalc "( ( ( (1.1-2) +3) * (2.5*2) ) + 10), (1.1 – 2) +3 * (2.5 * 2) + 10" Критерии оценки Оценка «удовлетворительно»: не предусмотрены скобки и приоритеты операций.

Оценка «хорошо»: учитываются приоритеты операций.

Оценка «отлично»: учитываются приоритеты операций, допускаются скобки.

Указания к выполнению задания ( http://ru.wikipedia.org/wiki/Обратная_польская_запись ).

Еще одним подходом к решению указанной задачи может быть использование структуры данных «стек». Данная структура представляет из себя список элементов организованных по принципу LIFO (англ. last in — first out, «последним пришел — первым вышел»). Одним из примеров стека может служить детская пирамидка, представляющая из себя ось, на которую одеваются кольца. Первым с такой пирамидки снимается кольцо, размещенное на ней последним. Размещение элемента в стеке обозначают операцией push, а извлечение элемента из стека – операцией pop.

Для решения указанной задачи потребуется два стека, первый будет использоваться для хранения операндов –num –(тип элемента – вещественное число), второй – ops – для хранения операций и скобок (тип элемента – символ).

Рассмотрим алгоритм, использующий стек, на примере выражения 1.1 – (5 +2 * (2 + 3)) / 10.

push(ops,'+') push(ops,'('), push(num,2) x = pop(num), y = pop(num) x = pop(num), y = pop(num) push(ops,'–'), push(ops,'/') 1,1; 15; '–'; '/'

ВАРИАНТ 2.3 ФОРМАТИРОВАНИЕ ИСХОДНОГО КОДА ПРОГРАММЫ НА ЯЗЫКЕ СИ

Задание Разработка инструмента Сformat, обеспечивающего автоматическое форматирование программ на языке Си. Команда Сformat принимает на вход имя файла, содержащего программу на языке Си.

Содержимое файла должно быть отформатировано согласно требованиям. Отформатированная программа не должна терять корректность. Если компилируется исходная программа, то должна компилироваться отформатированная.

Критерии оценки Оценка «удовлетворительно»: предусмотрена только расстановка табуляции на основании блоков операторов (количество табуляций равно числу символов '{').

Оценка «хорошо»: расстановка табуляций, изменение положения фигурных скобок и разбиение строк, превышающих максимально допустимую длину (80 символов).

Оценка «отлично»: в дополнение к требованиям оценки «хорошо» должна осуществляется проверка корректности расстановки фигурных, круглых и квадратных скобок (количество и последовательность должны быть правильными).

Указания к выполнению задания Проверка расстановки скобок осуществляется аналогично варианту 2.2.

К форматированию программы устанавливаются следующие требования:

1. Строка должна быть сдвинута на x табуляций вправо, где х определяется глубиной вложенности блока операторов. Например:

2. Фигурная скобка, открывающая блок операторов тела функции должна располагаться с новой строки, открывающая и закрывающая скобки имеют одинаковый отступ. Фигурная скобка, начинающая блок операторов цикла или ветвления должна располагаться на одной строке с закрывающейся круглой скобкой логического выражения. Закрывающая скобка располагается на одном уровне с ключевым словом конструкции. Например:

3. Каждый оператор (выражение заканчивающееся ";") должен располагаться с новой строки. В циклах и ветвлениях тело (ветвь) также должны располагаться с новой строки. Например:

4. Каждый оператор (выражение заканчивающееся ";") должен располагаться с новой строки.

Например:

5. Строки, длина которых превышает 80 символов, должны разбиваться. При разбиении строк необходимо учитывать, что ключевые слова, имена переменных и т.д. разбивать нельзя. Разбиение должно производиться по лексемам. Например (максимальная длина строки = 10 симв.):

x=test_var + my_long_test_var + 15; => my_long_test_var

ВАРИАНТ 2.4 АНАЛИЗ ИСХОДНОГО КОДА ПРОГРАММЫ НА ЯЗЫКЕ СИ

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

Критерии оценки Оценка «удовлетворительно»: Программа работает в интерактивном режиме. Пользователь задает с клавиатуры имя функции, а программа обнаруживает ее во входном файле и печатает номер строки и ее содержимое.

Оценка «хорошо»: осуществляется автоматический поиск всех функций объявленных (через прототип) или определенных в указанном файле. Для каждой из них производится подсчет количества ее вызовов в анализируемом файле.

Оценка «отлично»: в дополнение к требованиям оценки «хорошо» должно осуществляться построение таблицы глобальных и локальных переменных. В случае обнаружения конфликта (например, две переменные с одинаковым именем в функции) или перекрытия (локальная переменная перекрывает глобальную) должны выдаваться соответствующие предупреждения.

Указание к выполнению задания Рассмотрим работу программ на примере:

«удовлетворительно»:

Input function: func 13: func1(a);

ВАРИАНТ 2.5 ПРОВЕРКА ЦЕЛОСТНОСТИ ФАЙЛОВ

Задание Реализовать программу integrСtrl (Integrity Control) проверки целостности содержимого файловой системы. Использование программы состоит из двух шагов.

1. Запись информации о целостности в файл - базу данных. Для активации данного режима программа должна быть запущена с опцией –s (save integrity info). Если дополнительно указана опция –r, то рекурсивно анализируются все вложенные каталоги. Например:

$ integrСtrl -s -f database /home/alex/ # анализ только файлов alex и запись в database $ integrСtrl -s -r -f database /home/alex # анализ файлов alex и всех вложенных 2. Сверка информации о целостности, расположенной в указанном файле. Для активации данного режима необходимо использовать опцию –c (check integrity) $ integrСtrl -c -f database /home/alex/ # проверка директории /home/alex, рекурсивность Критерии оценки Оценка «хорошо»: проверка целостности ориентирована только на файлы, расположенные непосредственно в указанной директории (функционал опции –r не реализуется).

Оценка «отлично»: программа позволяет выполнить проверку целостности файлов, расположенных в указанной директории и во всех вложенных в нее.

Указание к выполнению задания Проверка целостности файлов должна осуществляться с применением технологии хеширования.

Для содержимого каждого обрабатываемого файла вычисляется значение хеш-функции с малой вероятностью коллизии. В рамках данной работы предлагается использование функции MD5. Для генерации хеш кодов MD5 рекомендуется использовать исходные коды, расположенные на сайте Кафедры ВС (http://cpct.sibsutis.ru/~artpol/downloads/prog/s2/MD5.tar.bz2) или реализацию в библиотеке OpenSSL (описание ее использования расположено по адресу: http://www.firststeps.ru/linux/r.php?18).

Для организации базы данных о целостности рекомендуется использовать бинарные файлы.

Предполагается, что структура каталогов не может изменяться. Перемещение директории рассматривается как ее удаление и создание нового каталога в другом месте. Рекомендованный формат одной файловой записи:

Название поля Комментарии Уникальный идентификатор записи в базе данных. Предназначен для описания структуры директорий.

Уникальный идентификатор родительской директории. Для исходного каталога (для которого формиparent_id руется информация о целостности) устанавливается в 0.

Если тип записи – файл, то данное поле содержит значение хеш-функции MD5, вычисленное для его Пример приведен на рисунке:

РАЗДЕЛ 3. ПОЛНОТЕКСТОВЫЙ ПОИСК ПО ШАБЛОНУ

Полнотекстовый поиск — поиск документа в базе данных текстов или в файловой системе (ФС) на основании содержимого этих документов, а также совокупность методов оптимизации этого процесса. Задания данного раздела предусматривают разработку программного обеспечения (ПО), позволяющего выполнять полнотекстовый поиск строк по шаблону (wildcard) в файлах, находящихся в указанной директории.

Задача поиска подстроки в строке (string matching problem).

Задача поиска всех фрагментов текста, которые совпадают с заданным образцом, например:

Образец: текст Существуют две основных трактовки понятия «текст»: «имманентная» (расширенная, философски нагруженная) и «репрезентативная»

(более частная). Имманентный подход подразумевает отношение к тексту как к автономной реальности, нацеленность на выявление его внутренней структуры. Репрезентативный — рассмотрение текста как особой формы представления знаний о внешней тексту действительности.

Результат полнотекстового поиска (в данном примере в виде выделения вхождений образца в тексте):

Существуют две основных трактовки понятия «текст»: «имманентная» (расширенная, философски нагруженная) и «репрезентативная»

(более частная). Имманентный подход подразумевает отношение к тексту как к автономной реальности, нацеленность на выявление его внутренней структуры. Репрезентативный – рассмотрение текста как особой формы представления знаний о внешней тексту действительности.

Формальная постановка задачи:

Пусть текст хранится в виде массива символов T[1 … n] длины n, а образец – в виде массива символов P[1 … m] длины m, m n. Элементы массивов P и T – символы конечного алфавита.

Основные соглашения, понятия и обозначения.

Подстроку х строки P, которая начинается в i-м символе и заканчивается в j-м символе будем обозначать через P[i, …, j]. Например, если P = “abcdefghijklmnop”, то P[2 … 6] = “bcdef”.

При изложении теоретического материала индексом первого элемента будет 1. При реализации алгоритмов на языке Си необходимо учитывать, что в нем индексом первого элемента является 0.

В большинстве кодировок (KOI-8, UTF-8, Windows-1251 и т.п.) коды первых 128 символов совпадают с таблицей ASCII. Для простоты изложения далее будем считать, то работа производится над текстами на английском языке, поэтому алфавит содержит символы таблицы ASCII. Рассмотренные далее понятия и методы могут быть распространены на символы любой кодировки. В рамках данной работы допускается работа только с английскими текстами.

Будем говорить, что образец P встречается в тексте Т со сдвигом s, если 0 s (n – m) и T[s + 1 … (s + m)] = P (или для любого j = 1 … m, T[s + j] = P[j]). Также можно сказать, что образец P встречается в тексте, начиная с позиции s. Далее будем считать операцию сравнения двух строк элементарной: T[s + 1 … (s + m)] = P, однако при реализации алгоритмов на языке программирования Си данное утверждение не справедливо. В программах на Си необходимо использовать функцию strcmp или strcmp.

Если образец P встречается в тексте T со сдвигом s (рис. 3.1, а.), то s называют допустимым сдвигом. В противном случае – недопустимым.

Множество строк конченой длины, которые можно составить из символов алфавита, будем обозначать через. Пустую строку (empty string) будем обозначать через. Длина строки x обозначается как |x|, конкатенация (склеивание, concatenation) строк x и y обозначается как xy, |xy| = |x| + |y|.

Строка называется префиксом (prefix) строки x ( ), если существует такая строка, что y = x (рис. 3.1, б). Строка называется суффиксом (suffix) строки x ( ), если существует тачто y = x (рис. 3.1, в). Из следует || |x|. Пустая строка является одновременно суффиксом и префиксом любой строки. Для любых строк x, y и символа a справедливо, Для краткости обозначим k-символьный префикс P[1 … k] образца P[1 … m] через Pk, тогда P0 =, Pm = P.

Тогда задачу поиска подстроки в строке можно сформулировать, как задачу поиска всех сдвигов s таких, что Будем говорить, что строки и x сравнимы ( ~ x), если одна из строк является суффиксом другой. Примерами сравнимых строк будут строки x, y и z из рис. 3.1, г, при этом справедливо как y ~ x, так и x ~ y.

Суффиксной функцией (suffix function) P(x), связанной с образцом P, называется функция, ставящая в соответствие некоторой строке x максимальную длину префикса P, который является суфрис. 3.2, а).

фиксом x:

Для любой строки x и символа a выполняется неравенство P(xa) P(x) + 1. Это значит, что появление нового символа может увеличить значение функции на 1, если Pka = Pk+1. В противном случае максимальная длина префикса P, являющаяся суффиксом xa уменьшится по сравнению с x. На рис. 3.2, б показано, что добавление к строке x символа 'd' приводит к увеличению P(xd) на 1 по сравнению с P(x). Увеличение на большее значение невозможно, так как добавлен лишь один символ.

Также на рисунке видно, что добавление символа 'a' значительно уменьшает значение P(xа).

Рис. 3.2 – Графическое доказательство неравенства суффикс-функции.

Префиксной функцией (prefix function) заданного образца P называют функцию P такую, что:

На рисунке 3.3 приведен пример вычисления значения функции P для элемента с номером 7.

Рассмотрим прямой алгоритм вычисления значений функции P для P = "abcdabcxabc"