1

所以我一直在研究子字符串搜索算法，发现大多数算法（如 kmp 和 rabin-karp 算法）在进行一些字符串匹配之前需要额外的时间复杂度来预处理时间。这样做有什么好处吗？为什么他们不直接跳到字符串匹配，以使大 O 时间复杂度不会下降到 O(m+n)？我尝试通过简单地跳过预处理时间来创建一个我认为是 O(n) 的子字符串算法（如果我错了，请纠正我）。我想知道为什么人们不这样做，请参阅下面的 C 代码。

int search(char hay[], char needle[], int hayLen, int needleLen){
    int found;
    int i = 0;

    while (i < (hayLen - needleLen + 1)){
        if (hay[i] == needle[0]){
            found = 1;
            for (int j=0; j<needleLen; j++){
                if (hay[i] != needle[j]){
                    found = 0;
                    break;
                }
                i++;
            }
            if (found)
                return i - needleLen;
        }
        else
            i++;
    }
    return -1;
}

编辑：

删除了 strlen 函数以避免任何不必要的时间复杂度

4

3 回答 3

8

老实说，这不是一个可怕的问题。我认为我们中的大多数人在尝试在发现 KMP 之前尝试创建字符串查找算法时都尝试过这样的解决方案。答案是这个贪心算法不起作用——它永远不会在i. 你可能会想“啊哈！这是针的开始！” 继续前进，直到发现“呃-哦！这不是全部针！”。在这个算法中，我们只向前推进，继续寻找针的起点。但是，实际针的开头可能是您认为是中间字符，同时试图贪婪地匹配尽可能多的针。

例如，aab和aaab。直到第三个a你才意识到“呃，哦，这毕竟不是针”，然后从第二个位置重新开始一个彻底的 O(nm) 算法，但你的算法只是向前推进，从未意识到aab从第二个位置开始。KMP 通过注意中间针的哪些部分也可能是针的潜在起点来解决这个问题。

于 2020-01-27T19:55:11.353 回答
5

好吧，您当前的代码是 O(n) 但是...

你的代码不起作用！

尝试这个：

int main()
{
    char a[] = "aaaab";
    char b[] = "aaab";
    if (search(a, b, strlen(a), strlen(b)) != -1) 
        printf("OK\n"); 
    else 
        printf("FAIL\n");
    return 0;
}

显然b可以找到，a但您的代码说它不存在。

问题是你总是递增i. 通过这样做，您确实会得到 O(n) ，但它也会使代码失败。

于 2020-01-27T19:46:35.597 回答
0

删除了 strlen 函数以避免任何不必要的时间复杂度

您删除了strlen调用，但现在必须将字符串的长度传递给函数：

int search(char hay[], char needle[], int hayLen, int needleLen)

那么......随着大小的增加，整个子字符串搜索的复杂性如何变化needle？毕竟不管是在函数内部还是函数外部计算长度，还是需要做的。O(m+n)意味着复杂度取决于 和 的needle长度haystack。

更极端地说，您可以编写一个 O(1)search函数，只需添加一个指示 in 位置的needle参数haystack。

于 2020-01-27T19:58:05.743 回答