php - PHP 使用什么子字符串算法(查找字符串)？

Question

我一直在试图找出什么子串算法(在另一个字符串中找到一个字符串)。 PHP的使用，我在GitHub上的PHP源码中找到了如下一段代码:

我认为它使用了 Bruteforce，但我不确定，这就是我在 SO 上寻求帮助的原因。

zend_memnstr(const char *haystack, const char *needle, size_t needle_len, const char *end) {
    const char *p = haystack;
    const char ne = needle[needle_len-1];
    ptrdiff_t off_p;
    size_t off_s;

    if (needle_len == 1) { 
        return (const char *)memchr(p, *needle, (end-p));
    }

    off_p = end - haystack;
    off_s = (off_p > 0) ? (size_t)off_p : 0;

    if (needle_len > off_s) {
        return NULL;
    }

    if (EXPECTED(off_s < 1024 || needle_len < 3)) {
        end -= needle_len;

        while (p <= end) {
            if ((p = (const char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
                if (!memcmp(needle, p, needle_len-1)) {
                    return p;
                }
            }
            if (p == NULL) {
               return NULL;
            }
            p++;
        }
        return NULL;
    } else {
        return zend_memnstr_ex(haystack, needle, needle_len, end);
    }
}

Answer 1

该函数遵循以下步骤:

• 它将 needle 的最后一个字符加载到 ne 中，从而在 needle_len 为 0 时调用未定义的行为.该字节将用于稍后代码中的通用循环。
• 它是 needle_len == 1 的特殊情况，将搜索委托(delegate)给标准库函数 memchr。
• 它计算要扫描的内存块的长度，允许 end 指向 haystack 之前，并在这种情况下返回 NULL。这是不一致的，因为此一致性检查仅针对 needle_len != 1 执行，并且 memchr 将传递很长的end - haystackif endpoints beforehaystack` 可能调用未定义的行为。
• 对于小于 1023 或 needle_len 小于 3 的长度，该函数根据 memchr 实现朴素算法。它扫描 needle 的第一个字节，手动检查潜在匹配的最后一个字节，并使用 memcmp 验证剩余的潜在匹配。这种方法是不一致的:如果needle_len是2，一个更简单的扫描会更有效，如果所有情况，应该少一个字节传递给memcmp 因为第一个字节已经匹配。
• 对于其他情况，haystack 长度超过 1022 且 needle 超过 2 个字节，该函数使用另一种在 zend_memnstr_ex 中实现的方法，它nwellnhof 表示是周日算法的变体。

有关高效字符串搜索的不同方法的更多解释:

• 一般文章:https://en.wikipedia.org/wiki/String_searching_algorithm
• 周日算法的详细信息:http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm