提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、Python数据结构与算法的详细介绍
- 1.Python中的常用的字符串算法
- 2.字符串算法
- 3.详细的字符串算法
- 1)KMP算法
- 2)Rabin-Karp算法
- 总结
前言
提示:这里可以添加本文要记录的大概内容:
第一天Python数据结构与算法的详细介绍
第二天五种常见的排序算法
第三天两种常见的搜索算法
第四天两种常见的递归算法
第五天一种常见的动态规划算法
第六天一种常见的贪心算法
第七天一种常见的分治算法
第八天一种常见的回溯算法
第九天六种常见的图论算法
第十天两种常见的字符串算法
提示:以下是本篇文章正文内容,下面案例可供参考
一、Python数据结构与算法的详细介绍
1.Python中的常用的字符串算法
以下是Python中的一些常用算法:
2.字符串算法
字符串算法:
- KMP算法:用于字符串匹配,时间复杂度O(n+m),其中n和m分别是文本和模式的长度。空间复杂度O(m)。
- Rabin-Karp算法:基于哈希的字符串匹配算法,时间复杂度平均O(n+m),最坏O(n*m)。空间复杂度O(1)(不考虑哈希表)。
3.详细的字符串算法
1)KMP算法
def compute_lps_array(pattern):"""计算部分匹配表(也称为最长前缀后缀数组或失败函数)"""length = 0 # 长度前缀后缀的公共元素lps = [0] * len(pattern) # 创建lps数组并初始化为0i = 1# 计算lps[i]直到i等于pattern的长度while i < len(pattern):if pattern[i] == pattern[length]:length += 1lps[i] = lengthi += 1else:# (length != 0)意味着我们之前找到了一个前缀后缀# 所以我们不能将长度设为0,因为我们可以通过减少长度来得到一个更小的前缀后缀if length != 0:length = lps[length - 1]# 如果pattern[i] != pattern[length],则我们不需要比较lps[i]# 我们只需要将i增加1else:lps[i] = 0i += 1return lpsdef kmp_search(text, pattern):"""KMP字符串搜索算法"""M = len(pattern)N = len(text)# 创建lps[]数组,它包含pattern的最长前缀后缀值lps = compute_lps_array(pattern)i = 0 # index for textj = 0 # index for patternwhile i < N:if pattern[j] == text[i]:i += 1j += 1if j == M:# 找到匹配项print(f"Found pattern at index {i - j}")j = lps[j - 1]# 当text[i] != pattern[j]时elif i < N and pattern[j] != text[i]:# 不要比较lps[0..lps[j-1]],因为它们不会产生匹配if j != 0:j = lps[j - 1]else:i += 1# 示例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)
2)Rabin-Karp算法
def rabin_karp_search(text, pattern, q=101):"""Rabin-Karp字符串搜索算法"""M = len(pattern)N = len(text)d = 256 # 假设字符集大小(对于ASCII字符)p = 0 # 模式字符串的哈希值t = 0 # 文本字符串的哈希值(初始子串)h = 1# 计算h = d^(M-1) % qfor _ in range(M - 1):h = (h * d) % q# 计算模式和文本第一个子串的哈希值for i in range(M):p = (d * p + ord(pattern[i])) % qt = (d * t + ord(text[i])) % q# 滑动窗口在文本上搜索for i in range(N - M + 1):# 检查哈希值是否匹配if p == t:# 检查实际字符串是否匹配for j in range(M):if text[i + j] != pattern[j]:breakelse:# 找到匹配项print(f"Found pattern at index {i}")# 计算下一个窗口的哈希值if i < N - M:t = (d * (t - ord(text[i]) * h) + ord(text[i + M])) % q# 处理负哈希值(当text[i] * h大于t时)if t < 0:t += q# 示例用法
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
rabin_karp_search(text, pattern)
总结
提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文简单介绍两种常见的字符串算法。