【轻松掌握数据结构与算法】字符串算法（String Algorithms）

字符串算法概述

字符串匹配算法是计算机科学中的一个重要领域，主要用于在文本中查找特定模式（子字符串）的出现位置。这些算法在文本编辑器、搜索引擎、生物信息学等领域有广泛的应用。

暴力法（Brute Force Method）

暴力法是最直接的字符串匹配算法，它通过逐个字符比较来查找模式在文本中的所有出现位置。

示例代码

def brute_force_search(text, pattern):
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i  # 模式在文本中的起始位置
    return -1  # 模式未找到

# 示例输入输出
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
print(brute_force_search(text, pattern))  # 输出: 15

Rabin-Karp 字符串匹配算法

Rabin-Karp 算法使用哈希函数来快速查找模式在文本中的所有出现位置。它通过计算模式和文本子字符串的哈希值来减少不必要的比较。

示例代码

def rabin_karp_search(text, pattern, prime, d):
    n = len(text)
    m = len(pattern)
    p = 0  # 模式的哈希值
    t = 0  # 文本子字符串的哈希值
    h = 1  # 哈希函数的最高次项系数

    # 计算 h, p 和 t
    for i in range(m - 1):
        h = (h * d) % prime
    for i in range(m):
        p = (d * p + ord(pattern[i])) % prime
        t = (d * t + ord(text[i])) % prime

    # 滑动窗口查找模式
    for i in range(n - m + 1):
        if p == t:
            # 通过逐个字符比较确认匹配
            for j in range(m):
                if text[i + j] != pattern[j]:
                    break
            else:
                return i  # 模式在文本中的起始位置
        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % prime
            if t < 0:
                t += prime
    return -1  # 模式未找到

# 示例输入输出
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
prime = 101
d = 256
print(rabin_karp_search(text, pattern, prime, d))  # 输出: 15

使用有限自动机的字符串匹配

有限自动机（Finite Automaton, FA）是一种状态机，用于在文本中查找模式。它通过预处理模式构建一个状态转移表，然后在文本中进行匹配。

示例代码

def compute_transition_function(pattern, alphabet):
    m = len(pattern)
    transition = {}
    for q in range(m + 1):
        for a in alphabet:
            k = min(m + 1, q + 2)
            while k > 0 and not (pattern[:q] + a).endswith(pattern[:k]):
                k -= 1
            transition[(q, a)] = k
    return transition

def finite_automaton_search(text, pattern):
    n = len(text)
    m = len(pattern)
    alphabet = set(text)
    transition = compute_transition_function(pattern, alphabet)
    q = 0
    for i in range(n):
        q = transition.get((q, text[i]), 0)
        if q == m:
            return i - m + 1  # 模式在文本中的起始位置
    return -1  # 模式未找到

# 示例输入输出
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
print(finite_automaton_search(text, pattern))  # 输出: 15

KMP 算法

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它通过预处理模式构建一个部分匹配表（Partial Match Table），然后在文本中进行匹配，避免了不必要的回溯。

示例代码

def compute_lps_array(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 = len(text)
    m = len(pattern)
    lps = compute_lps_array(pattern)
    i = 0  # 文本索引
    j = 0  # 模式索引
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            return i - j  # 模式在文本中的起始位置
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1  # 模式未找到

# 示例输入输出
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
print(kmp_search(text, pattern))  # 输出: 15

Boyer-Moore 算法

Boyer-Moore 算法是一种高效的字符串匹配算法，它通过从右向左比较字符，利用坏字符规则和好后缀规则来跳过不必要的比较。

示例代码

def bad_char_heuristic(pattern, alphabet):
    m = len(pattern)
    bad_char = {char: -1 for char in alphabet}
    for i in range(m):
        bad_char[pattern[i]] = i
    return bad_char

def good_suffix_heuristic(pattern):
    m = len(pattern)
    suffix = [0] * m
    prefix = [False] * m
    for i in range(m - 1):
        j = i
        while j >= 0 and pattern[j] == pattern[m - 1 - i + j]:
            j -= 1
        suffix[i] = j + 1
        if j == -1:
            prefix[i] = True
    return suffix, prefix

def boyer_moore_search(text, pattern):
    n = len(text)
    m = len(pattern)
    alphabet = set(text)
    bad_char = bad_char_heuristic(pattern, alphabet)
    suffix, prefix = good_suffix_heuristic(pattern)
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            return i  # 模式在文本中的起始位置
        x = j - bad_char.get(text[i + j], -1)
        y = 0
        if j < m - 1:
            y = m - 1 - j + suffix[j]
            if not prefix[j]:
                y = m - 1 - j + suffix[j]
            else:
                y = m - suffix[m - 1]
        i += max(x, y)
    return -1  # 模式未找到

# 示例输入输出
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
print(boyer_moore_search(text, pattern))  # 输出: 15

存储字符串的数据结构

哈希表（Hash Tables）

哈希表是一种基于哈希函数的数据结构，用于存储键值对。它通过哈希函数将键映射到表中的位置，然后将键值对存储在该位置。

二叉搜索树（Binary Search Trees）

二叉搜索树是一种有序的二叉树，每个节点的值大于其左子树的所有节点值，小于其右子树的所有节点值。它支持高效的插入、删除和查找操作。

字典树（Tries）

字典树是一种用于存储字符串集合的树形数据结构。每个节点代表一个字符，从根节点到某个节点的路径代表一个前缀。字典树支持高效的前缀查找和字符串插入操作。

三叉搜索树（Ternary Search Trees）

三叉搜索树是一种结合了二叉搜索树和哈希表优点的数据结构。每个节点有三个子节点：左子节点、中子节点和右子节点。它支持高效的插入、删除和查找操作。

后缀树（Suffix Trees）

后缀树是一种用于存储字符串所有后缀的树形数据结构。每个节点代表一个后缀，从根节点到某个节点的路径代表一个后缀。后缀树支持高效的子字符串查找和模式匹配操作。

示例代码：字典树（Trie）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = 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_of_word = 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_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# 示例输入输出
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # 输出: True
print(trie.search("app"))    # 输出: False
print(trie.starts_with("app"))  # 输出: True

示例代码：后缀树（Suffix Tree）

class SuffixTreeNode:
    def __init__(self, start, end, suffix_link=None):
        self.start = start
        self.end = end
        self.suffix_link = suffix_link
        self.children = {}

class SuffixTree:
    def __init__(self, text):
        self.text = text
        self.root = SuffixTreeNode(-1, -1)
        self.build()

    def build(self):
        for i in range(len(self.text)):
            self.add_suffix(i)

    def add_suffix(self, start):
        node = self.root
        for j in range(start, len(self.text)):
            if self.text[j] not in node.children:
                node.children[self.text[j]] = SuffixTreeNode(j, len(self.text))
            node = node.children[self.text[j]]

    def search(self, pattern):
        node = self.root
        for char in pattern:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# 示例输入输出
text = "banana"
suffix_tree = SuffixTree(text)
print(suffix_tree.search("ana"))  # 输出: True
print(suffix_tree.search("apple"))  # 输出: False

字符串算法: 问题与解决方案

问题1：实现一个函数，检查一个字符串是否是另一个字符串的子串

问题描述：给定两个字符串 s1 和 s2，检查 s1 是否是 s2 的子串。

示例代码：

def is_substring(s1, s2):
    return s1 in s2

# 示例输入输出
s1 = "abc"
s2 = "abcde"
print(is_substring(s1, s2))  # 输出: True

s1 = "xyz"
s2 = "abcde"
print(is_substring(s1, s2))  # 输出: False

问题2：实现一个函数，找到一个字符串在另一个字符串中所有出现的位置

问题描述：给定两个字符串 s1 和 s2，找到 s1 在 s2 中所有出现的位置。

示例代码：

def find_all_occurrences(s1, s2):
    occurrences = []
    start = 0
    while start < len(s2):
        pos = s2.find(s1, start)
        if pos != -1:
            occurrences.append(pos)
            start = pos + 1
        else:
            break
    return occurrences

# 示例输入输出
s1 = "abc"
s2 = "abcdeabc"
print(find_all_occurrences(s1, s2))  # 输出: [0, 5]

s1 = "xyz"
s2 = "abcde"
print(find_all_occurrences(s1, s2))  # 输出: []

问题3：实现一个函数，检查一个字符串是否是回文

问题描述：给定一个字符串 s，检查它是否是回文。

示例代码：

def is_palindrome(s):
    return s == s[::-1]

# 示例输入输出
s = "racecar"
print(is_palindrome(s))  # 输出: True

s = "hello"
print(is_palindrome(s))  # 输出: False

问题4：实现一个函数，找到一个字符串的最长回文子串

问题描述：给定一个字符串 s，找到它的最长回文子串。

示例代码：

def longest_palindromic_substring(s):
    if not s:
        return ""
    n = len(s)
    start, max_length = 0, 1

    def expand_around_center(left, right):
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(n):
        left1, right1 = expand_around_center(i, i)
        left2, right2 = expand_around_center(i, i + 1)

        if right1 - left1 + 1 > max_length:
            start = left1
            max_length = right1 - left1 + 1
        if right2 - left2 + 1 > max_length:
            start = left2
            max_length = right2 - left2 + 1

    return s[start:start + max_length]

# 示例输入输出
s = "babad"
print(longest_palindromic_substring(s))  # 输出: "bab" 或 "aba"

s = "cbbd"
print(longest_palindromic_substring(s))  # 输出: "bb"

问题5：实现一个函数，找到两个字符串的最长公共子串

问题描述：给定两个字符串 s1 和 s2，找到它们的最长公共子串。

示例代码：

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0
    end = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end = i
            else:
                dp[i][j] = 0

    return s1[end - max_length:end]

# 示例输入输出
s1 = "ABABC"
s2 = "BABCA"
print(longest_common_substring(s1, s2))  # 输出: "BABC"

s1 = "ABC"
s2 = "DEF"
print(longest_common_substring(s1, s2))  # 输出: ""

问题6：实现一个函数，找到一个字符串的最短唯一前缀

问题描述：给定一个字符串数组 strs，找到每个字符串的最短唯一前缀。

示例代码：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

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.count += 1

    def shortest_unique_prefix(self, word):
        node = self.root
        prefix = ""
        for char in word:
            prefix += char
            node = node.children[char]
            if node.count == 1:
                return prefix
        return prefix

def shortest_unique_prefixes(strs):
    trie = Trie()
    for word in strs:
        trie.insert(word)
    return [trie.shortest_unique_prefix(word) for word in strs]

# 示例输入输出
strs = ["dog", "cat", "apple", "apricot", "fish"]
print(shortest_unique_prefixes(strs))  # 输出: ["d", "c", "app", "apr", "f"]

问题7：实现一个函数，检查一个字符串是否可以通过删除一些字符变成另一个字符串的子序列

问题描述：给定两个字符串 s1 和 s2，检查 s1 是否可以通过删除一些字符变成 s2 的子序列。

示例代码：

def is_subsequence(s1, s2):
    iter_s2 = iter(s2)
    return all(char in iter_s2 for char in s1)

# 示例输入输出
s1 = "abc"
s2 = "ahbgdc"
print(is_subsequence(s1, s2))  # 输出: True

s1 = "axc"
s2 = "ahbgdc"
print(is_subsequence(s1, s2))  # 输出: False

问题8：实现一个函数，找到一个字符串的所有回文子串

问题描述：给定一个字符串 s，找到它的所有回文子串。

示例代码：

def all_palindromic_substrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    palindromes = []

    for i in range(n):
        dp[i][i] = True
        palindromes.append(s[i:i+1])

    for start in range(n-1, -1, -1):
        for end in range(start+1, n):
            if s[start] == s[end]:
                if end - start == 1 or dp[start+1][end-1]:
                    dp[start][end] = True
                    palindromes.append(s[start:end+1])

    return palindromes

# 示例输入输出
s = "abc"
print(all_palindromic_substrings(s))  # 输出: ['a', 'b', 'c']

s = "aaa"
print(all_palindromic_substrings(s))  # 输出: ['a', 'a', 'a', 'aa', 'aa', 'aaa']

以上是“String Algorithms”中的一些常见问题及其解决方案。这些问题涵盖了字符串匹配、子串查找、回文检查、最长公共子串、最短唯一前缀和子序列检查等多个方面。希望这些示例代码和输入输出能帮助您更好地理解和应用字符串算法。

总结

字符串匹配算法在计算机科学中有广泛的应用。暴力法、Rabin-Karp 算法、有限自动机、KMP 算法和 Boyer-Moore 算法是几种常见的字符串匹配算法，每种算法都有其特定的用途和优缺点。此外，哈希表、二叉搜索树、字典树、三叉搜索树和后缀树是用于存储和处理字符串的常用数据结构。希望这些示例代码和输入输出能帮助您更好地理解和应用字符串算法。