PHP源码阅读strstr

发表于

strstr

搜索字符串在另一字符串中的第一次出现，并返回剩余部分。

时间复杂度

O(n+m)

源码

strstr实现思路是，先查询子串的位置，返回该位置后的字符串。核心函数是 zend_memnstr_ex，使用的子串搜索算法是Sunday算法，这个具体就不说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// zend_memnstr_ex
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])];  // 如果查询失败，通过跳转表决定搜索从搜索串什么位置开始
}
// zend_memnstr_ex_pre 构造跳转表
// Sunday算法重要的一部分，构造跳转表
// 跳转表是个256位长的数组
for (i = 0; i < 256; i++) {
	td[i] = needle_len + 1;
}
if (reverse) {
	for (i = needle_len - 1; i >= 0; i--) {
		td[(unsigned char)needle[i]] = i + 1;
	}
} else {
	for (i = 0; i < needle_len; i++) {
		// 例如子串是 aba
		// 最后跳转表，td = array('a' => 1, 'b' => 2, '其他' => 4)
		td[(unsigned char)needle[i]] = (int)needle_len - i;
	}
}

例子

1
strstr('bfabceabadde', 'aba');

1、zend_memnstr_ex_pre 构造跳转表，如下：

a b 其他
1 2 4

2、查询过程

b f a b c e a b a d d e
1 a b a
2 a b a
3 a b a 
1
2
3
4
5
第一步，b ！= a，源码第9行，跳出来；接着，源码19行，查找下一个查询从哪里开始；
p += td[(unsigned char)(p[needle_len])]，此时的p[needle_len]为'b'；
相当于，p += td['b']，看跳转表，p += 2，所以跳到了第二步的位置；
如果使用朴素算法，时间复杂度就是O(n*m)了。