PHP 提供的字符串匹配函数多是单模式匹配，因此大多通过 KMP 算法实现，我们以 strstr函数为例，简单对底层实现源码进行剖析。
strstr 是 PHP 标准库提供的函数，所以可以在 ext/standard/string.c 中找到其定义：
PHP_FUNCTION(strstr)
{
zval *needle;
zend_string *haystack;
const char *found = NULL;
char needle_char[2];
zend_long found_offset;
zend_bool part = 0;
ZEND_PARSE_PARAMETERS_START(2, 3)
Z_PARAM_STR(haystack)
Z_PARAM_ZVAL(needle)
Z_PARAM_OPTIONAL
Z_PARAM_BOOL(part)
ZEND_PARSE_PARAMETERS_END();
if (Z_TYPE_P(needle) == IS_STRING) {
if (!Z_STRLEN_P(needle)) {
php_error_docref(NULL, E_WARNING, "Empty needle");
RETURN_FALSE;
}
found = php_memnstr(ZSTR_VAL(haystack), Z_STRVAL_P(needle), Z_STRLEN_P(needle), ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
} else {
if (php_needle_char(needle, needle_char) != SUCCESS) {
RETURN_FALSE;
}
needle_char[1] = 0;
found = php_memnstr(ZSTR_VAL(haystack), needle_char, 1, ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
}
if (found) {
found_offset = found - ZSTR_VAL(haystack);
if (part) {
RETURN_STRINGL(ZSTR_VAL(haystack), found_offset);
} else {
RETURN_STRINGL(found, ZSTR_LEN(haystack) - found_offset);
}
}
RETURN_FALSE;
}
阅读这段源码可知，真正的匹配逻辑通过 php_memnstr 函数实现，我们继续溯源，可以追踪到 Zend/zend_operators.h 文件中的 zend_memnstr 函数定义，核心匹配逻辑在这里：
static zend_always_inline const char *
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 < 9)) { /* glibc memchr is faster when needle is too short */
end -= needle_len;
while (p <= end) {
if ((p = (const char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
if (!memcmp(needle+1, p+1, needle_len-2)) {
return p;
}
}
if (p == NULL) {
return NULL;
}
p++;
}
return NULL;
} else {
return zend_memnstr_ex(haystack, needle, needle_len, end);
}
}
如果模式串（待匹配字符串）长度为1，只需通过 C 函数 memchr 来检索即可；如果模式串长度大于主串长度，则直接返回 NULL；如果主串长度或者模式串长度很短，也是直接通过 memcmp 函数检索，这样更快；否则将通过 zend_memnstr_ex 函数来匹配：
ZEND_API const char* ZEND_FASTCALL zend_memnstr_ex(const char *haystack, const char *needle, size_t needle_len, const char *end)
{
unsigned int td[256];
register size_t i;
register const char *p;
if (needle_len == 0 || (end - haystack) < needle_len) {
return NULL;
}
zend_memnstr_ex_pre(td, needle, needle_len, 0);
p = haystack;
end -= needle_len;
while (p <= end) {
for (i = 0; i < needle_len; i++) {
if (needle[i] != p[i]) {
break;
}
}
if (i == needle_len) {
return p;
}
if (UNEXPECTED(p == end)) {
return NULL;
}
p += td[(unsigned char)(p[needle_len])];
}
return NULL;
}
很显然这是一段 KMP 算法实现，next 数组通过 zend_memnstr_ex_pre 函数生成。
所以综合来看，strstr 的时间复杂度就是 KMP 算法的时间复杂度，是 O(n+m)，其中 n 是主串长度，m 是模式串长度。
strpos 函数和 strstr 函数底层实现原理一样，你可以参考 strstr 函数的源码分析思路去查看。