前言
"color: #ff0000">1. BF算法
"application/x-tex">Bruce-ForceBruce"application/x-tex">S=ABACABABS=ABACABAB,模式串
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
2. KMP算法
"normal">.
"normal">"
"false">(
"normal">′
"text-align: center">"text-align: left">"text-align: center">"text-align: left">"normal">"
"normal">"
"text-align: left">"normal">"
"normal">"
"normal">"
"normal">"
"text-align: left">如果模式串8号位与主串当前位不匹配,找最长公共前后缀,指针前面的子串为
"text-align: left">
位编号
1
2
3
4
5
6
7
8
索引
0
1
2
3
4
5
6
7
模式串
A
B
A
A
B
C
A
C
next
-1
0
0
1
1
2
0
1
"text-align: center">"text-align: left">"application/x-tex">T_j=T_tTj"false">[
"normal">≠
"htmlcode">
def getNext(substrT): next_list = [-1 for i in range(len(substrT))] j = 0 t = -1 while j < len(substrT) - 1: if t == -1 or substrT[j] == substrT[t]: j += 1 t += 1 # Tj=Tt, 则可以到的next[j+1]=t+1 next_list[j] = t else: # Tj!=Tt, 模式串T索引为t的字符与当前位进行匹配 t = next_list[t] return next_list def KMP(substrS, substrT, next_list): count = 0 j = 0 t = 0 while j < len(substrS) and t < len(substrT): if substrS[j] == substrT[t] or t == -1: # t == -1目的就是第一位匹配失败时 # 主串位置加1, 匹配串回到第一个位置(索引为0) # 匹配成功, 主串和模式串指针都后移一位 j += 1 t += 1 else: # 匹配失败, 模式串索引为t的字符与当前位进行比较 count += 1 t = next_list[t] if t == len(substrT): # 这里返回的是索引 return j - t, count+1 else: return -1, count+1
3. KMP算法优化版
"application/x-tex">S=AAABAAAABS=AAABAAAAB,模式串
"text-align: left">"application/x-tex">SS的4号位为模式串
"false">[
def getNextval(substrT): nextval_list = [-1 for i in range(len(substrT))] j = 0 t = -1 while j < len(substrT) - 1: if t == -1 or substrT[j] == substrT[t]: j += 1 t += 1 if substrT[j] != substrT[t]: # Tj=Tt, 但T(j+1)!=T(t+1), 这个就和next数组计算时是一样的 # 可以得到nextval[j+1]=t+1 nextval_list[j] = t else: # Tj=Tt, 且T(j+1)==T(t+1), 这个就是next数组需要更新的 # nextval[j+1]=上一次的nextval_list[t] nextval_list[j] = nextval_list[t] else: # 匹配失败, 模式串索引为t的字符与当前位进行比较 t = nextval_list[t] return nextval_list
"htmlcode">
if __name__ == '__main__': S1 = 'ABACABAB' T1 = 'ABAB' S2 = 'AAABAAAAB' T2 = 'AAAAB' print('*' * 50) print('主串S={0}与模式串T={1}进行匹配'.format(S1, T1)) print('{:*^25}'.format('KMP')) next_list1 = getNext(T1) print('next数组为: {}'.format(next_list1)) index1_1, count1_1 = KMP(S1, T1, next_list1) print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index1_1, count1_1)) print('{:*^25}'.format('KMP优化版')) nextval_list1 = getNextval(T1) print('nextval数组为: {}'.format(nextval_list1)) index1_2, count1_2 = KMP(S1, T1, nextval_list1) print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index1_2, count1_2)) print('') print('*' * 50) print('主串S={0}与模式串T={1}进行匹配'.format(S2, T2)) print('{:*^25}'.format('KMP')) next_list2 = getNext(T2) print('next数组为: {}'.format(next_list2)) index2_1, count2_1 = KMP(S2, T2, next_list2) print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index2_1, count2_1)) print('{:*^25}'.format('KMP优化版')) nextval_list2 = getNextval(T2) print('nextval数组为: {}'.format(nextval_list2)) index2_2, count2_2 = KMP(S2, T2, nextval_list2) print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index2_2, count2_2))
"application/x-tex">S=ABACABABS=ABACABAB与模式串
结束语
在写本篇博客之前也是反复看参考书、视频,边画图边去理解它,这篇博客也是反复修改了好几次,最终算是把KMP解决掉了,有关字符串知识的复习也算是基本结束,下面就是刷题了(虽然在LeetCode做过了几道题)。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
RTX 5090要首发 性能要翻倍!三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。
据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。
更新日志
- 群星《前途海量 电影原声专辑》[FLAC/分轨][227.78MB]
- 张信哲.1992-知道新曲与精丫巨石】【WAV+CUE】
- 王翠玲.1995-ANGEL【新艺宝】【WAV+CUE】
- 景冈山.1996-我的眼里只有你【大地唱片】【WAV+CUE】
- 群星《八戒 电影原声带》[320K/MP3][188.97MB]
- 群星《我的阿勒泰 影视原声带》[320K/MP3][139.47MB]
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[320K/MP3][148.91MB]
- 刘雅丽.2001-丽花皇后·EMI精选王【EMI百代】【FLAC分轨】
- 齐秦.1994-黄金十年1981-1990CHINA.TOUR.LIVE精丫上华】【WAV+CUE】
- 群星.2008-本色·百代音乐人创作专辑【EMI百代】【WAV+CUE】
- 群星.2001-同步过冬AVCD【环球】【WAV+CUE】
- 群星.2020-同步过冬2020冀待晴空【环球】【WAV+CUE】
- 沈雁.1986-四季(2012梦田复刻版)【白云唱片】【WAV+CUE】
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[FLAC/分轨][257.88MB]
- 《国语老歌 怀旧篇 3CD》[WAV/分轨][1.6GB]