_
prerequisite
- mergesort思想, 单调指针(monotonic pointer)
- 笛卡尔积dfs的非递归计算方法 或者 非递归实现 itertools.combinations
- python 编程语言相关知识, 尤其是generator
- 不需要知道KMP算法以及相关概念
这篇文章用形式化语言讲会特别特别长, 所以只能用接近意会的方式了
难度 codeforce 1800分
没有相关OJ题目, 正确性靠自测
~
这篇文章介绍如何用带有通配符的字符串进行搜索
例如
'*'符号可以用来匹配单个的任意字符
P="ab*c", T="abec"
P在T出现过一次
或者'*'符号可以用来匹配任意长度子串
P="ab*c", T="abeec"
P可以匹配T
引用的代码
以下代码不需要看懂
以下代码在字符串T中搜索P的所有出现的位置,
时间复杂度O(|T|+|P|), 空间复杂度O(|P|)
|
def border(s): n = len(s) B = [None] * n B[0] = ml = 0 for i in range(1, n): # loop inv: ml is B[i-1] while ml > 0 and s[i] != s[ml]: ml = B[ml - 1] if s[i] == s[ml]: ml += 1 B[i] = ml return B
def search(T, P): """ yield all index j that T[j:j+np]==P """ B = border(P) # B is border array of P ml = 0 np, nt = len(P), len(T) for i in range(nt): while ml > 0 and T[i] != P[ml]: ml = B[ml - 1] if T[i] == P[ml]: ml += 1 if ml == np: yield i + 1 - np ml = B[ml - 1] |
notation
|
P np |
用来搜索的字符串 len(P) |
|
T nt |
被搜索的字符串 len(T) |
'*'可以匹配单个字符
让P在'*'处分裂, 例如
`P="abc*def*gh"`, 分裂为 `["abc","def","gh"]`
这些P子串, 记作Psub[i]
用KMP算法, 在T中搜索"abc"和"def"和"gh",
得到的三个结果是有序的,
接下来枚举T中所有可能位置 i, T[i:i+np] == P
由 T[i:i+np] == P 这个条件, 可以推出Ps[i]在T中应具有的位置
(类似于mergesort的思想)创建len(Ps)个单调递增的索引即可
节省空间的措施
Ps[i]在T中的搜索结果可以不用都存起来, 每次只获取一个结果
python中可以用`yield`关键字实现
代码
|
def search_wild(T, P): np = len(P) nt = len(T)
Ps = []
prv = 0 for cur in range(np + 1): if cur == np or P[cur] == '*': if cur - prv > 0: Ps.append([prv, search(T, P[prv:cur]), None]) prv = cur + 1 nk = len(Ps) for iT in range(nt - np + 1): for ik in range(nk): while Ps[ik][2] == None or (Ps[ik][2] < iT + Ps[ik][0]): try: Ps[ik][2] = next(Ps[ik][1]) except StopIteration: return
if Ps[ik][2] != iT + Ps[ik][0]: break
else: # the length of matched substring is determined yield iT |
时间,空间复杂度
O( nk * nt + np ), O( nk )
'*'可以匹配任意长度子串
同样让P在'*'处分裂,
不过P不能以`*`开头, 不能以`*`结尾, 本来是搜索T中子串, 加个'*'没有意义, 还会导致程序运行时间复杂度过高
如代码所示, 在'*'处分裂P, 得到 nk 个P的子串
把这些子串在T中的搜索结果存起来, 得到一个 nk 列的表
对所有表进行笛卡尔积(类似) 得到结果
代码
|
def search_wild_match2(T, P): P = P.strip('*') np = len(P) if np == 0: # this is meaningless and time complexity become O(2^t) raise Exception("not valid")
Ps = []
prv = 0 for cur in range(np + 1): if cur == np or P[cur] == '*': if cur - prv > 0: indices = list(search(T, P[prv:cur])) if len(indices)==0: return Ps.append([cur - prv, indices, 0]) # Ps[i][2] is index on Ps[i][1] # Ps[i][1][ Ps[i][2] ] is index on T prv = cur + 1
# similar to pylib.itertools.combinations nk = len(Ps) def iToiT(i): return Ps[i][1][ Ps[i][2] ] for i in range(1, nk): while Ps[i][2] < len(Ps[i][1]) and iToiT(i) < iToiT(i-1) + Ps[i - 1][0]: Ps[i][2] += 1 if Ps[i][2] == len(Ps[i][1]): return
while True: yield tuple(Ps[i][1][Ps[i][2]] for i in range(nk)) last = None for i in reversed(range(nk)): if Ps[i][2] < len(Ps[i][1]) - 1: last = i break else: break
Ps[last][2] += 1 for i in range(last + 1, nk): while Ps[i][2] < len(Ps[i][1]) and iToiT(i) < iToiT(i-1) + Ps[i - 1][0]: Ps[i][2] += 1 if Ps[i][2] == len(Ps[i][1]): return |
时间,空间复杂度
O(( nt / nk )^ nk + np ) , O( nt + np )