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

#c #алгоритм

Нужно было сделать поиск фразы в книге и возвратить кол-во совпадений и время поиска.
Все алгоритмы кроме Кнута получились. Алгоритм Кнута тоже получился,но преподаватель
говорит, что он медленно работает. Вот функция:

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. Время
почти не отличилось. Что не так с алгоритмом? Подскажите пожалуйста.    

Ответы

Ответ 1

В общем разобрался. Во-первых, в моём алгоритме вычисляется префикс функция лишние
разы, поэтому нужно делать без цикла. Много скорости не прибавит, если маленький текст
и большая поисковая строка. Но когда много исходного текста, алгоритм Кнута обходит
наивный алгоритм во много раз.
Итак, вот исправленная функция:
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\n", count_finds, t2-t1);