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

Question

Привет, я пытаюсь написать версию 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; 
} 

Answer 1

Простой ответ в первом цикле я ++ оседает перед следующим [я] = у так на последний символ строки поиска ее пытаются установить следующее [M + 1] J - который вызывает исключение индекса за пределы. Пользуйтесь сменой заказа:

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

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

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

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

[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 
}