Помогите исправить мой алгоритм поиска KMP - PullRequest
Новая
       21

Помогите исправить мой алгоритм поиска KMP

0 голосов
/ 13 октября 2010

Здравствуйте, я пытаюсь написать C # версию KMP search из алгоритма в книге C. Не могу найти ошибку в моем алгоритме. Кто-нибудь поможет? 

static int KMP(string p, string str) {
    int m = p.Length;
    int n = str.Length;
    int i;
    int j;

    int[] next = new int[m];
    next[0] = -1;

    for (i = 0, j = -1; i < m; i++, j++, next[i] = j) { 
                                        //Getting index out of bounds
        while (j > 0 && p[i] != p[j]) j = next[j];
    }

    for (i = 0, j = 0; i < n && j < m; i++, j++) {
        while (j >= 0 && p[j] != str[i]) j = next[j];
        if (j == m) return i - m;
    }

    return -1;
}

1 Ответ

1 голос
/ 14 октября 2010

Простой ответ в первом цикле: i ++ устанавливается перед следующим [i] = j, поэтому в последнем символе строки поиска он пытается установить для следующего [m + 1] значение j - что приводит к выходу индекса за пределыисключение.Попробуйте изменить порядок: 

for (i = 0, j = -1; i < m;  next[i] = j, i++, j++)

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

public int[] BuildTable(string word)
{
    // todo
}

и некоторых тестов NUnit на основе описания вики 

[Test]
public void Should_get_computed_table_0_0_0_0_1_2_given_ABCDABD()
{
    const string input = "ABCDABD";
    var result = BuildTable(input);
    result.Length.ShouldBeEqualTo(input.Length);
    result[0].ShouldBeEqualTo(-1);
    result[1].ShouldBeEqualTo(0);
    result[2].ShouldBeEqualTo(0);
    result[3].ShouldBeEqualTo(0);
    result[4].ShouldBeEqualTo(0);
    result[5].ShouldBeEqualTo(1);
    result[6].ShouldBeEqualTo(2);
}

[Test]
public void Should_get_computed_table_0_1_2_3_4_5_given_AAAAAAA()
{
    const string input = "AAAAAAA";
    var result = BuildTable(input);
    result.Length.ShouldBeEqualTo(input.Length);
    result[0].ShouldBeEqualTo(-1);
    result[1].ShouldBeEqualTo(0);
    result[2].ShouldBeEqualTo(1);
    result[3].ShouldBeEqualTo(2);
    result[4].ShouldBeEqualTo(3);
    result[5].ShouldBeEqualTo(4);
    result[6].ShouldBeEqualTo(5);
}

Далее напишите один или несколько тестов для метода KMP. 

[Test]
public void Should_get_15_given_text_ABC_ABCDAB_ABCDABCDABDE_and_word_ABCDABD()
{
    const string text = "ABC ABCDAB ABCDABCDABDE";
    const string word = "ABCDABD";
    int location = KMP(word, text);
    location.ShouldBeEqualTo(15);
}

Затем реализуйте, используя структуру, использованную в вики-описании алгоритма, и он должен собраться вместе для вас. 

public int KMP(string word, string textToBeSearched)
{
    var table = BuildTable(word);
    // rest of algorithm
}
...