【第十天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-两种常见的字符串算法（持续更新）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言

提示：这里可以添加本文要记录的大概内容：

第一天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数组并初始化为0
    i = 1
 
    # 计算lps[i]直到i等于pattern的长度
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            # (length != 0)意味着我们之前找到了一个前缀后缀
            # 所以我们不能将长度设为0，因为我们可以通过减少长度来得到一个更小的前缀后缀
            if length != 0:
                length = lps[length - 1]
            # 如果pattern[i] != pattern[length]，则我们不需要比较lps[i]
            # 我们只需要将i增加1
            else:
                lps[i] = 0
                i += 1
 
    return lps
 
def kmp_search(text, pattern):
    """KMP字符串搜索算法"""
    M = len(pattern)
    N = len(text)
 
    # 创建lps[]数组，它包含pattern的最长前缀后缀值
    lps = compute_lps_array(pattern)
 
    i = 0  # index for text
    j = 0  # index for pattern
 
    while i < N:
        if pattern[j] == text[i]:
            i += 1
            j += 1
 
        if 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) % q
    for _ in range(M - 1):
        h = (h * d) % q
 
    # 计算模式和文本第一个子串的哈希值
    for i in range(M):
        p = (d * p + ord(pattern[i])) % q
        t = (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]:
                    break
            else:
                # 找到匹配项
                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)

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文简单介绍两种常见的字符串算法。

作者：Long_poem