Brute-Force算法，
简称为 BF算法，是一种简单朴素的模式匹配算法，常用于在一个主串 S 内查找一个子串 T 的出现位置。
它的核心思想与操作是：
对于给定的主串 S 与子串 P ，主串 S 的长度为 N，子串 T 的长度为 M ；
首先，将 S[1] 和 T[1] 进行比较；
若相等，则再比较 S[2] 和 T[2] ，一直到 T[M] 为止；
若 S[1] 和 T[1] 不等，则 T 向右移动一个字符的位置，再依次进行比较；
""" 0 1 2 3 4 S a c b c d T c d s = 0 t = 0 S a c b c d T c d s = 1 t = 0 S a c b c d T c d s = 2 t = 1 S a c b c d T c d s = 2 t = 0 S a c b c d T c d s = 3 t = 0 S a c b c d T c d s = 4 t = 1 """
代码实现
def searchIndex(S, T): s, t, pos = 0, 0, 0 S_len = len(S) T_len = len(T) while (s < S_len and t < T_len): print(s, t) if S[s] == T[t]: s += 1 t += 1 else: pos += 1 s = pos t = 0 if t == T_len: return pos else: return -1 print(searchIndex("abdabc", "abc")) """ 0 0 1 1 2 2 1 0 2 0 3 0 4 1 5 2 3 """
BF算法 在主串和字串匹配失败时，主串进行的回溯操作会影响效率，回溯之后，主串与字串有些部分比较是没有必要的。这种简单的丢弃前面的匹配信息是 BF算法 之所以效率低效的一个重要因素。
参考：
