Результаты работы
Время
Размерность
строки
Рис. 5. Сравнение временных затрат на поиск алгоритмами КМП и БМ
На рис. 5 синим цветом отмечен алгоритм БМ, оранжевым – КМП. Согласно информации с графика, алгоритм КМП медленнее алгоритма БМ. Также стоит отметить, что алгоритм КМП сильнее замедляется с увеличением размерности строки. В связи с этим можно сказать, что алгоритм КМП в среднестатистической ситуации, когда искомая подстрока может находиться, как в начале, так и в любой другой части строки, предпочтительнее БМ благодаря своей более низкой сложности.
Приложение
-
#include <iostream> #include <stdlib.h> #include <conio.h> #include <time.h> #include <chrono> #include <cstring> #include <fstream> #define k1 10000 using namespace std;
int BMSearch(char* str, const char* word)//Алгоритм поиска Бойера-Мура { int N=strlen(str); int M=strlen(word); int* d=new int[256]; int i; for(i=0;i<256;i++) d[i]=M; for(i=0;i<M-1;i++) d[(unsigned char)word[i]]=M-i-1; int result = -1; for(i=M;i<=N;i+=d[(unsigned char)str[i-1]]) { int j, k; for(j=M-1, k=i-1;j>=0 && str[k]==word[j]; k--, j--); if(j<0) { result=i-M; break; } } delete [] d; if (result > 200001) return -1; return result; }
char getRandomChar()//Функция случайного символа { const char str[] = {'A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H', 'h', 'I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o', 'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v', 'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z'}; return str[rand() % 52]; //любая из 52 букв }
int KMPSearch(char *string, char *substring)//Алгоритм поиска Кнута-Морриса-Пратта { //в качестве параметров в функцию передается строка и субстрока int sl, ssl; int res = -1; sl = strlen(string); //присваивается длина строки ssl = strlen(substring); //присваивается длина субстроки if ( sl == 0 ) //проверка строки cout << "Неверно задана строка\n"; else if ( ssl == 0 ) //проверка субстроки cout << "Неверно задана подстрока\n"; else {
///----------------------------------------///префикс функция int i, j = 0, k = -1; int *d; d = new int[1000]; d[0] = -1; while ( j < ssl - 1 ) {//пока j < кол-ва эл-тов строки while ( k >= 0 && substring[j] != substring[k]) k = d[k]; j++; k++; if ( substring[j] == substring[k] ) d[j] = d[k]; else d[j] = k; } ///----------------------------------------/// i = 0; j = 0; while ( j < ssl && i < sl ) {//пока j < длины субстроки и i < длины строки while ( j >= 0 && string[i] != substring[j] ) j = d[j]; i++; j++; } delete [] d; res = j == ssl ? i - ssl : -1; } return res; }
void arr_cmp(int n, int time, float &kmp_t, float &bm_t)//Рекурсивная ф-ия сравнения { time--; int m=4;//длина субстроки char *arr = new char[n]; char *subs = new char[m]; for (int i=0; i<n; i++) arr[i]=getRandomChar(); for (int h=0; h<m; h++) subs[h] = getRandomChar(); auto start = chrono::steady_clock::now(); int kmp_r = KMPSearch(arr, subs); auto finish = std::chrono::steady_clock::now(); kmp_t+=chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count(); cout << "kmp time: " <<chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count()<<" ns\t\t"; cout << "kmp_rez: "<< kmp_r << endl; start = chrono::steady_clock::now(); int bm_r = BMSearch(arr, subs); finish = std::chrono::steady_clock::now(); bm_t+=chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count(); cout << "bm time: " <<chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count()<<" ns\t\t"; cout << "bm_rez: "<< bm_r << endl; delete [] arr; delete [] subs; if (time!=0) arr_cmp(n, time, kmp_t, bm_t); }
int main() { int times = 1000;//количество повторов int stepcount = 20;//количество шагов cout << "Rekomenduetsya vvodit chislo ot 1000\n"; cout << "vvedite kolichestvo povtornih poiskov: "; cin >> times; float kmp_time = 0; float *kmp_av = new float[stepcount];//массив значений для КМП float kr_time = 0; float *kr_av = new float[stepcount];//массив значений для БМ for (int i=1; i<=stepcount; i++) { int size = (k1*i); cout << size << endl; arr_cmp(size, times, kmp_time, kr_time); cout << times << " times\n"; kmp_av[i-1]=kmp_time/times; kmp_time = 0; kr_av[i-1]=kr_time/times; kr_time = 0; } ///Вывод---------------------------------------------------------------------/// cout << " count \t time\n"; fstream fout ("rez.txt", ios::out); fout << "kmp_time \tbm_time \n"; for (int i=1; i<=stepcount; i++) { printf(" %i \t %7.2f \t %7.2f\n" ,i*k1, kmp_av[i-1], kr_av[i-1]); fout << kmp_av[i-1] << "\t" << kr_av[i-1] << endl; }
fout.close(); delete [] kmp_av; delete [] kr_av; getch(); return 0; }
Санкт-Петербург
2020