大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
今天就跟大家聊聊有关深入浅析Python数据结构KMP,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。
创新互联专注于耿马企业网站建设,响应式网站,商城建设。耿马网站建设公司,为耿马等地区提供建站服务。全流程按需规划网站,专业设计,全程项目跟踪,创新互联专业和态度为您提供的服务1. BF算法
BF算法,即Bruce−ForceBruce-ForceBruce−Force算法,又称暴力匹配算法。其思想就是将主串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。
假设主串S=ABACABABS=ABACABABS=ABACABAB,模式串T=ABABT=ABABT=ABAB,每趟匹配失败后,主串S指针回溯,模式串指针回到头部,然后再次匹配,过程如下:
def BF(substrS, substrT): if len(substrT) > len(substrS): return -1 j = 0 t = 0 while j < len(substrS) and t < len(substrT): if substrT[t] == substrS[j]: j += 1 t += 1 else: j = j - t + 1 t = 0 if t == len(substrT): return j - t else: return -1