Нужно было сделать поиск фразы в книге и возвратить кол-во совпадений и время поиска. Все алгоритмы кроме Кнута получились. Алгоритм Кнута тоже получился,но преподаватель говорит, что он медленно работает. Вот функция:
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\n", count_finds-1, t2-t1);
Я пробовал также без цикла делать, считать совпадения внутри knuth_morris. Время почти не отличилось. Что не так с алгоритмом? Подскажите пожалуйста.