gpt4 book ai didi

c# - 帮助修复我的 KMP 搜索算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:34:44 25 4
gpt4 key购买 nike

您好,我正在尝试编写 KMP search 的 C# 版本来自 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;
}

最佳答案

简单的答案是在第一个循环中 i++ 在 next[i] = j 之前稳定下来,因此在搜索字符串的最后一个字符上它试图将 next[m+1] 设置为 j - 这会导致索引越界异常(exception)。尝试更改顺序:

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

然后使用算法的 wiki 描述中使用的结构来实现,它应该会为您准备好。

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

关于c# - 帮助修复我的 KMP 搜索算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3925063/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com