O(n) 子串算法

Question

所以我一直在研究子字符串搜索算法，发现大多数算法（如 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 函数以避免任何不必要的时间复杂性

Answer 1

好吧，您当前的代码是 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) 但它也会使代码失败。

Answer 2

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

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

Answer 3

removed the strlen function to avoid any unwanted time complexities

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

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

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

为了把这一点发挥到极致，您可以通过添加一个参数来编写一个 O(1) search 函数，该参数指示 needle 在 haystack 中的位置。

O(n) 子串算法

O(n) substring algorithm

c

algorithm

substring

knuth-morris-pratt

rabin-karp