字符串处理相关算法

1. 字符串翻转算法

字符串翻转算法是指将给定的字符串按倒序排列。例如，给定字符串 "algorithm"，翻转后为 "mhtirogla"。

实现该算法的一个简单方法是使用循环迭代法，即从字符串的两侧开始同时向中间遍历，并交换对应位置上的字符。

示例代码：

def reverse_string(s: str) -> str:
    str_list = list(s)
    left, right = 0, len(s) - 1
    while left < right:
        str_list[left], str_list[right] = str_list[right], str_list[left]
        left += 1
        right -= 1
    return "".join(str_list)

2. 字符串匹配算法

字符串匹配算法是指对给定的文本串和模式串进行匹配，找到模式串在文本串中第一次出现的位置。例如，给定文本串 "hello world" 和模式串 "world"，则匹配成功，返回位置5。

KMP算法是一种常用的字符串匹配算法，它的核心思想是利用已知信息跳过一些不必要的比较，从而提高匹配效率。

示例代码：

def kmp(text: str, pattern: str) -> int:
    # 构建模式串的next数组
    j, m = 0, len(pattern)
    next_val = [-1] * m
    while j < m - 1:
        if k == -1 or pattern[j] == pattern[k]:
            j += 1
            k += 1
            next_val[j] = k
        else:
            k = next_val[k]
    # 在文本串中查找模式串
    i, n = 0, len(text)
    j = 0
    while i < n and j < m:
        if j == -1 or text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = next_val[j]
    if j == m:
        return i - m
    else:
        return -1

3. 最长公共子序列算法

最长公共子序列（LCS）算法是指对于两个给定的字符串，找到它们的最长公共子序列。例如，给定字符串 "abcde" 和 "ace"，则它们的LCS为 "ace