Алгоритм сопоставления строк KMP: выход вспомогательного массива - PullRequest
Новая
       8

Алгоритм сопоставления строк KMP: выход вспомогательного массива

1 голос
/ 26 марта 2012

Это моя реализация алгоритма сопоставления строк KMP .Когда я проверяю массив пи, он хранит 0,1,2,3,4,5,6.Но согласно альго-книгам это должно быть 0,0,1,2,3,0,1.Мой код также дает правильный результат. Я не понимаю, почему это происходит, или я делаю что-то не так?и если да, пожалуйста, поправьте меня.

спасибо. 

#include<iostream>
#include<string>
#include<string.h>

using namespace std;

int* ComputePrefix(char P[])
{
    size_t m = strlen(P);
    int *pi = new int[m];
    pi[0] = 0;
    int k = 0;

    for(int q =0; q < m; q++)
    {
        if( k > 0 && P[k+1] != P[q])
            k = pi[k];

        if( P[k+1] == P[q])
            {
                pi[q] = k;
                k = k + 1;
            }
            pi[q]=k;
    }

    return (pi);
}

void KMP_Matcher(char T[], char P[])
{

    size_t n = strlen(T);
    size_t m = strlen(P);

    int *pi = new int[m];
    pi = ComputePrefix(P);

    cout<<endl;


    int q =0;
    for (int i = 0; i <= n; i++)
    {
        if( q > 0 && P[q] != T[i] )
        {
            q = pi[q - 1];
        }


        else if( P[q] == T[i])
        {


            if( q == m-1)
            {
                cout<<"Shift occurs at : "<< i-q <<endl;
                q = pi[q];
            }
            else q = q + 1;
        }

        else q++;
    }
}


int main()
{
    char T[] = "abababacaba";
    char P[] = "ababaca";

    KMP_Matcher(T,P);
    return 0;
}

1 Ответ

1 голос
/ 26 марта 2012

Ваша функция построения таблицы переходов просто не проверяет стрелки на префиксы. Мы хотим иметь возможность искать для каждой позиции в игле длину самого длинного возможного правильного префикса иглы, ведущей в (но не включая) это положение, кроме начала полного префикса на needle[0], который просто не соответствует; это то, как далеко мы должны вернуться в поиске следующего матча. Следовательно, каждая запись в таблице переходов (скажем, table[i]) точно равна длине максимально длинного правильного префикса иглы, который также является префиксом подстроки, заканчивающейся на needle[i - 1].

Первые две записи в таблице переходов - это -1 и 0, так как a) несоответствие в начале шаблона не приводит к обратному отслеживанию (или, другими словами, префикс нулевой длины не может иметь никаких надлежащих префиксов или суффиксы) и б) считается, что пустая строка имеет длину 0.

Для более подробной информации, пожалуйста, посмотрите Википедию или учебник по алгоритмам.

Код для выполнения вышесказанного: 

int *build_jump_table(const char * target)
{
    if(!target)
        return NULL;
    int *table = new int[strlen(target) + 1];
    if(!table)
        return NULL;
    table[0] = -1; /* unused by the matcher, just used here */

    for(int i = 0; target[i] != '\0'; i++) {
        table[i+1] = table[i] + 1;
        while(table[i+1] > 0 && target[i] != target[table[i+1] - 1]) {
            table[i + 1] = table[table[i + 1] - 1] + 1;
        }
    }
    return table;
}

, что довольно многословно и может быть значительно упрощено, если вы понимаете концепцию таблицы прыжков.

...