Описание программы
Сама программа включает в себя несколько функций, как:
int BMSearch(char* str, const char* word)
int KMPSearch(char *string, char *substring)
char getRandomChar()
void arr_cmp(int n, int time, float &kmp_t, float &bm_t)
Функция 1 является алгоритмом Бойера-Мура, в качестве аргументов получает ссылки на массив основной строки и массив субстроки, которую необходимо найти. В качестве результата возвращает индекс первого элемента, с которого пошло совпадение. В обратном случае возвращается «-1», что сигнализирует об отсутствии результата.
Функция 2 является алгоритмом Кнута-Морриса-Пратта и работает по такому же принципу, что и функция 1 – получает ссылки на массив основной строки и подстроки, возвращает результат.
Функция 3 является служебной функцией, используемой для заполнения массивов строки и подстроки. При помощи метода rand библиотеки stdlib.h возвращает случайный символ из 52 символов – строчных и заглавных латинских букв.
Функция 4 является функцией для проведения сравнения временных затрат двух функций – 1 и 2. В качестве аргументов получает размерность массива, в котором будет проходить поиск подстроки (int n), количество повторов (int time), адрес переменной, в которой суммируется всё время, подсчитанное для алгоритма КМП (float &kmp_t), аналогично для алгоритма БМ (float &bm_t). В теле функции создаётся динамический массив указанной размерности – строка, в которой будет происходить поиск. Далее она заполняется случайными символами при помощи функции 3. То же самое происходит для подстроки, только с небольшим отличием – её размерность фиксирована и равняется 4. Это оптимальный размер, при котором вероятен и успех поиска, и его провал. Далее посредством методов библиотеки chrono инициализируется подсчет времени для функции 2. Выглядит это следующим образом: перед обращением к функции в переменную start заносятся данные о текущем времени, далее инициализируется сама функция, а после фиксируется момент её завершения в переменную finish. Эти данные необходимо преобразовать, потому что на данный момент они являют собой лишь две даты. Для этого посредством методов библиотеки chrono вычитается start из finish, тем самым получая готовый результат – время, затраченное для поиска. Этот результат суммируется с тем, что находится в переменной kmp_t. Полностью аналогичный принцип работы соблюдается для алгоритма поиска БМ. После всех манипуляций, связанных с подсчётом времени, освобождается память, занятая динамическими массивами строки и подстроки, после чего, если это не последний прогон, к функции происходит еще одно обращение.
В int main() происходят основные операции, необходимые для выполнения поставленной задачи: здесь инициализируется количество повторов (int times) и количество шагов (int stepcount, под шагом подразумевается число, на которое будет увеличиваться размер основной строки, в программе он указан командой препроцессора #define k1 10000). Далее инициализируются динамические массивы для хранения средних результатов подсчета времени для КМП и БМ соответственно: float *kmp_av = new float[stepcount]; float *kr_av = new float[stepcount];. После всего этого объявляется цикл for (int i=1; i<=stepcount; i++), в котором производятся временные расчёты для размеров основной строки от 10 тысяч до 200 тысяч. В теле цикла находится обращение к функции 4 и обработка полученных результатов – деление всей суммы на количество повторных обращений.
После этого цикла нет необходимости в какой-либо дальнейшей обработке, поэтому полученные результаты выводятся на консоль посредством функции printf и в файл посредством методов библиотеки fstream. После всех проделанных манипуляций освобождается память от занятых динамических массивов, закрывается файл и завершается работа программы.