簡單的回答是在第一環路I ++是下一個之前沉降[I] = j的等搜索字符串的最後一個字符其試圖設置下一個[M + 1]到j - 這會導致一個索引超出界限例外。嘗試更改順序:
for (i = 0, j = -1; i < m; next[i] = j, i++, j++)
更基本的是,嘗試將實現分解爲可測試部分。例如,您可以爲第一個循環提取可測試方法,因爲它正在爲搜索詞構建計算表。首先:
public int[] BuildTable(string word)
{
// todo
}
以及基於Wiki描述
[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方法的一個或多個測試一些NUnit tests。
[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
}