Алгоритм поиска Кнута Морриса

Нужно было сделать поиск фразы в книге и возвратить кол-во совпадений и время поиска. Все алгоритмы кроме Кнута получились. Алгоритм Кнута тоже получился,но преподаватель говорит, что он медленно работает. Вот функция: int knuth_morris(char *text, char *pattern, int pos) { int i, j; int result = -1; int *T = NULL;
if (pattern[0] == '\0') return 0;
/* Вычисление префикс-функции */ T = (int *) malloc((strlen(pattern)+1) * sizeof (int)); T[0] = -1; for (i=0; pattern[i] != '\0'; i++) { T[i+1] = T[i] + 1; while (T[i+1] > 0 && pattern[i] != pattern[T[i+1]-1]) T[i+1] = T[T[i+1]-1] + 1; }
/* Поиск */ j=0; for (i=pos; text[i] != '\0'; ) { if (j < 0 || text[i] == pattern[j]) { ++i, ++j; if (pattern[j] == '\0') { result = i-j; break; } } else j = T[j]; }
free(T); return result; } И использую её так: t1 = omp_get_wtime(); while(pos!=-1) { pos = knuth_morris(book_text, substr, pos+sz_substr); count_finds++; } t2 = omp_get_wtime(); printf("Knuth-Morris-Pratt Algoritm: %d matches. Time: %lf
", count_finds-1, t2-t1); Я пробовал также без цикла делать, считать совпадения внутри knuth_morris. Время почти не отличилось. Что не так с алгоритмом? Подскажите пожалуйста.

Ответ

В общем разобрался. Во-первых, в моём алгоритме вычисляется префикс функция лишние разы, поэтому нужно делать без цикла. Много скорости не прибавит, если маленький текст и большая поисковая строка. Но когда много исходного текста, алгоритм Кнута обходит наивный алгоритм во много раз. Итак, вот исправленная функция: int knuth_morris(char *text, char *pattern) { int *T = NULL; int i, j; int result = -1; int count_finds = 0;
if (pattern[0] == '\0') return 0;
/* Вычисление префикс-функции */ T = (int *) malloc((strlen(pattern)+1) * sizeof *T); T[0] = -1; for (i=0; pattern[i] != '\0'; i++) { T[i+1] = T[i] + 1; while (T[i+1] > 0 && pattern[i] != pattern[T[i+1]-1]) T[i+1] = T[T[i+1]-1] + 1; }
/* Поиск */ j=0; for (i=0; text[i] != '\0'; ) { if (j < 0 || text[i] == pattern[j]) { ++i, ++j; if (pattern[j] == '\0') { count_finds++; /*result = i-j; break; */ } } else j = T[j]; }
free(T); return count_finds; } И её использование: t1 = omp_get_wtime(); count_finds = knuth_morris(book_text, substr); t2 = omp_get_wtime(); printf("Knuth-Morris-Pratt Algoritm: %d matches. Time: %lf
", count_finds, t2-t1);