j******2
发帖数: 362 | 1 假如haystack的长度为n，needle的长度为m，我觉得应该是O(n)。
最坏情况比如haystack是"abcabcabc"，needle是"abcd"，比较的次数也就是4+1+1+4+1
+1+4+1+1，大约就是2n。
各位觉得呢？ |
R******1
发帖数: 58 | 2 是O(n),但是我觉得比你想的复杂。
可以参考KMP： http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
+1
【在 j******2 的大作中提到】
: 假如haystack的长度为n，needle的长度为m，我觉得应该是O(n)。
: 最坏情况比如haystack是"abcabcabc"，needle是"abcd"，比较的次数也就是4+1+1+4+1
: +1+4+1+1，大约就是2n。
: 各位觉得呢？
|
r*******e
发帖数: 7583 | 3 咋就直接跟m没关系了？
按你的数法，最坏情况显然是O(m*n)
haystack = 01010101010101010101010101010101010101010101010101010...
needle = 010101010101010101011
+1
【在 j******2 的大作中提到】
: 假如haystack的长度为n，needle的长度为m，我觉得应该是O(n)。
: 最坏情况比如haystack是"abcabcabc"，needle是"abcd"，比较的次数也就是4+1+1+4+1
: +1+4+1+1，大约就是2n。
: 各位觉得呢？
|
d*********g
发帖数: 154 | 4
嗯应该是这样，如果是KMP的话就是O(n)了~
【在 r*******e 的大作中提到】
: 咋就直接跟m没关系了？
: 按你的数法，最坏情况显然是O(m*n)
: haystack = 01010101010101010101010101010101010101010101010101010...
: needle = 010101010101010101011
:
: +1
|
