defBF(s, p): ''' Brute-Force算法实现字符串匹配 ''' indies = [] n = len(s) m = len(p) for i in range(n - m + 1): index = i for j in range(m): if s[index] == p[j]: index += 1 else: break if index - i == m: indies.append(i) return indies
defgetNextList(s): n = len(s) nextList = [0, 0] j = 0 for i in range(1, n): while j > 0and s[i] != s[j]: j = nextList[j] if s[i] == s[j]: j += 1 nextList.append(j) return nextList
defKMP(s, p): ''' Knuth-Morris-Pratt算法实现字符串匹配 ''' n = len(s) m = len(p) nextList = getNextList(p) indies = [] j = 0 for i in range(n): while s[i] != p[j] and j > 0: j = nextList[j]
if s[i] == p[j]: j += 1 if j == m: indies.append(i-m+1) j = nextList[j] return indies