動機

Z algo

z[i]是看這個位置i開始，與從0開始的string，有多長是一樣的

所以可以把pattern接到要比對的字串最前面，之後產生z function，去找與pattern一樣長的位置

那重點就是怎麼產生z function? z function是從i開始往前看，所以可以利用前面已經看過的z[i]來加速

假設有一個已經生完z[i]的範圍(最靠右)

  1. 看i是不是在範圍中，同時看利用之前的z[i-l]延伸出去，如果還在範圍，就抄答案
  2. 不能抄答案就重新算
def mk_z(S):
	z = [0]*len(S)
	l, r = 0, 1

	def extend(l, r):
		while r <= len(S) and S[r-l-1] == S[r-1]:
			r += 1
		return r
	# [l,r)
	# most examples use [i,r], which is closed range
	# I dont like closed range, so I use [l,r) to rewrite this prog
	for i in range(1,len(S)):
		# ((l) ... i) ..z[i-l].. r
		if i < r and i+z[i-l] < r-1: # i+z[i-l] is extended str, and this is in range
			z[i] = z[i-l] # so we can compute z[i] directly
		else: # i is not in [l,r) or i+z[i-l] >= r-1, so we need a new [l,r)
			l = i # new range
			r = extend(l, i+1 if i >= r else r) # use new end & extend
			z[i] = r-l-1 # new [l,r), new z[i] (compute)
	return z

def z_algo(S,pat):
	magic = f'{pat}.{S}' # '.' must not exist in S & pat
	z = mk_z(magic)
	offset = len(pat)+1
	for i in range(offset, len(magic)):
		if z[i] == len(pat):
			return f'found at {i-offset}'
	return 'no found'