7

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

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 ответ 1

6

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

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);

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.