字符串算法

字符串算法:

字符串算法是一类用于处理字符串操作和匹配的问题的算法，通常在文本处理、数据分析以及搜索领域中应用广泛。以下是一些常见的字符串算法和相关技术：

1. 字符串匹配算法

• 朴素匹配算法（Naive Algorithm） 从字符串的每个位置开始逐一比较子串是否匹配，时间复杂度为

  $$
  𝑂 ( 𝑛 × 𝑚 )，适用于小型数据。
  $$

• KMP（Knuth-Morris-Pratt）算法 使用部分匹配表（Partial Match Table，或前缀表）加速模式匹配，避免重复比较。时间复杂度为

  $$
  O(n+m)
  $$

• Boyer-Moore算法 基于字符跳跃规则的算法，对长文本和短模式匹配效果较优。时间复杂度最坏情况

  $$
  O(n×m)，但通常情况下更高效。
  $$

• Rabin-Karp算法 通过哈希函数实现模式匹配，用于快速查找，时间复杂度为

  $$
  O(n+m)（均摊）。
  $$

2. 字符串搜索与分析

• 最长公共子串（Longest Common Substring） 动态规划或后缀数组求解，时间复杂度为

  $$
  O(n×m)或O(n+m)（后缀数组）。
  $$

• 最长公共子序列（Longest Common Subsequence, LCS） 动态规划实现，时间复杂度

  $$
  O(n×m)，用于分析相似度。
  $$

• 最长回文子串 动态规划或中心扩展法，时间复杂度

  $$
  O(n^2)，Manacher算法优化到 O(n)。
  $$

• 编辑距离（Edit Distance/Levenshtein Distance） 动态规划算法用于计算两个字符串的最小编辑操作次数，时间复杂度

  $$
  O(n×m)
  $$

3. 字符串压缩与编码

• 哈夫曼编码 使用频率构建最优二叉树以压缩数据。

• Run-Length Encoding（RLE） 简单的压缩算法，压缩连续重复字符。

• BWT（Burrows-Wheeler Transform） 用于字符串排序和压缩的转换技术。

4. 高级数据结构

• Trie树（前缀树） 高效存储和查找字符串集合，适用于自动补全和词典树问题。

• 后缀树与后缀数组 用于快速模式匹配和子串分析，时间复杂度通常为

  $$
  O(n)
  $$

  。

• AC自动机（Aho-Corasick Automaton） 多模式串匹配算法的实现，用于高效搜索多个子串。

5. 哈希技术

• 滚动哈希（Rolling Hash） 应用于子串匹配（如 Rabin-Karp），可以快速更新子串的哈希值。

• 字符串去重与查找 利用哈希表实现高效的重复检测。

应用场景

• 文本编辑器：拼写检查、搜索替换。

• 数据压缩：文件和字符串的压缩与编码。

• 网络安全：检测重复、过滤恶意内容。

• 基因序列分析：相似度匹配与子序列分析。

根据需求选择合适的算法和数据结构，以优化性能。

代码示例:

以下是几种字符串算法的代码示例，分别用 Python 实现。

1. 朴素字符串匹配

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i + m] == pattern:
            print(f"Pattern found at index {i}")

示例调用：

naive_search("abracadabra", "abra")

2. KMP 算法

def compute_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps
​
def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    lps = compute_lps(pattern)
    i = j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

示例调用：

kmp_search("ababcabcabababd", "ababd")

3. 最长回文子串（中心扩展法）

def longest_palindromic_substring(s):
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    longest = ""
    for i in range(len(s)):
        # 奇数长度
        odd = expand_around_center(i, i)
        # 偶数长度
        even = expand_around_center(i, i + 1)
        longest = max(longest, odd, even, key=len)
    return longest

示例调用：

print(longest_palindromic_substring("babad"))

4. Trie 树的实现

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
​
class Trie:
    def __init__(self):
        self.root = TrieNode()
​
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
​
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

示例调用：

trie = Trie()
trie.insert("hello")
print(trie.search("hello"))  # True
print(trie.search("hell"))   # False

5. Rabin-Karp 算法

def rabin_karp(text, pattern, base=256, prime=101):
    n, m = len(text), len(pattern)
    hpattern = 0
    htext = 0
    h = 1
​
    for i in range(m - 1):
        h = (h * base) % prime
​
    for i in range(m):
        hpattern = (hpattern * base + ord(pattern[i])) % prime
        htext = (htext * base + ord(text[i])) % prime
​
    for i in range(n - m + 1):
        if hpattern == htext:
            if text[i:i + m] == pattern:
                print(f"Pattern found at index {i}")
        if i < n - m:
            htext = (htext * base - ord(text[i]) * h + ord(text[i + m])) % prime
            if htext < 0:
                htext += prime

示例调用：

rabin_karp("abracadabra", "abra")

这些代码可以直接运行并测试不同的输入案例。根据实际场景选择合适的算法以优化性能。