Python 子字符串搜索的对抗性输入

Question

子字符串搜索的 CPython 实现（例如通过 in）是通过以下算法实现的。

def find(s, p):
    # find first occurrence of p in s
    n = len(s)
    m = len(p)
    skip = delta1(p)[p[m-1]]
    i = 0
    while i <= n-m:
        if s[i+m-1] == p[m-1]: # (boyer-moore)
            # potential match
            if s[i:i+m-1] == p[:m-1]:
                return i
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + skip # (horspool)
        else:
            # skip
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + 1
    return -1 # not found

至少，根据 CPython 实现的作者 (?) 编写的 this source (taken from this older answer)。

同一来源提到该算法的最坏情况复杂度为 O(nm)，其中 n 和 m 是两个字符串的长度。我对这个界限是否紧密感兴趣。我的问题是：

Are there adversarial examples for the algorithm used in Python in? Can we give a sequence of pairs of strings (pattern, string) so that running pattern in string takes quadratic (or at least superlinear) time?

标准示例演示了朴素子字符串搜索的二次最坏情况运行时间，其中 string = 'a'*n 和 pattern = 'a'*m + b does not work。

Answer 1

试试这个：

import re
import time

def slow_match(n):
    pat = 'a' + ('z' * n)
    str = 'z' * (n + n)
    start_time = time.time()
    if re.search(pat, str):
        print("Shouldn't happen")
    print(("Searched", n, time.time() - start_time))

slow_match(10000)
slow_match(50000)
slow_match(100000)
slow_match(300000)

Answer 2

s='a'*n 和 p='a'*m+'b' 的天真例子因为行

行不通

if s[i+m-1] == p[m-1]:

这将检查 p ('b') 的最后一个字符（不是第一个）与 s 中相应的当前位置。由于失败，结果只是 s 上的一次迭代，这就是它如此之快的原因。

如果你翻转p（s='a'*n和p='b'+'a'*m），那么会发生类似的事情——这次上面的行通过了（p的最后一个字符是现在 'a')，但随后 p 向前迭代，因此很快找到 'b'，因此这个示例再次是线性且快速的。

对显示 O(nm) 行为的天真示例的简单更改是 s='a'*n 和 p='a'*m+'ba'。在这种情况下，p 的最后一个字符是 'a'，所以初始检查通过了，但是在到达 [=15= 之前它需要遍历 p 的其余部分].

# full='a'*n; sub='a'*m+'b'
>>> timeit("sub in full", "sub='a'*10+'b'; full='a'*100")
0.13620498299860628
>>> timeit("sub in full", "sub='a'*10+'b'; full='a'*1000")
0.9594046580004942
>>> timeit("sub in full", "sub='a'*100+'b'; full='a'*1000")
0.9768632190007338
# Linear in n, but m has minimal effect: ~O(n)

# full='a'*n; sub='a'*m+'ba'
>>> timeit("sub in full", "sub='a'*10+'ba'; full='a'*100")
0.35251976200015633
>>> timeit("sub in full", "sub='a'*10+'ba'; full='a'*1000")
3.4642483099996753
>>> timeit("sub in full", "sub='a'*100+'ba'; full='a'*1000")
27.152958754999418
# Both n and m have linear effect: ~O(nm)

Python 子字符串搜索的对抗性输入

Adversarial inputs for Python substring search

python

string

algorithm

complexity-theory

time-complexity