正文

学会串匹配，ACM竞赛轻松应对

/0 浏览量
0621

在ACM竞赛中，字符串匹配问题是一个常见且重要的算法问题。掌握高效的字符串匹配算法，对于提高竞赛成绩有着至关重要的作用。本文将详细介绍几种常用的字符串匹配算法，帮助你在ACM竞赛中轻松应对。

1. KMP算法

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法。它的核心思想是避免重复比较已经确定不匹配的字符，从而提高匹配效率。

1.1 算法原理

KMP算法通过预处理模式串，构造一个部分匹配表（也称为“失败函数”），在匹配过程中，当发生不匹配时，可以利用部分匹配表直接跳过一些不必要的比较。

1.2 代码实现

def kmp_search(s, p):
    # 构建部分匹配表
    def build_partial_match_table(p):
        m = len(p)
        lps = [0] * m
        length = 0
        i = 1
        while i < m:
            if p[i] == p[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    n = len(s)
    lps = build_partial_match_table(p)
    i = j = 0
    while i < n:
        if p[j] == s[i]:
            i += 1
            j += 1
        if j == m:
            return i - j
        elif i < n and p[j] != s[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

# 示例
s = "ABABDABACDABABCABAB"
p = "ABABCABAB"
print(kmp_search(s, p))  # 输出：10

2. Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，其核心思想是从后向前匹配，并利用坏字符规则和好后缀规则来提高匹配效率。

2.1 算法原理

Boyer-Moore算法通过预处理模式串，构造两个规则：坏字符规则和好后缀规则。在匹配过程中，根据这两个规则，算法可以跳过一些不必要的比较。

2.2 代码实现

def boyer_moore_search(s, p):
    def build_bad_char_table(p):
        m = len(p)
        bad_char = [-1] * 256
        for i in range(m - 1):
            bad_char[ord(p[i])] = i
        return bad_char

    def build_good_suffix_table(p):
        m = len(p)
        good_suffix = [0] * m
        i = m - 1
        j = m - 1
        while j >= 0:
            if p[i] == p[j]:
                good_suffix[i] = j + 1
                i -= 1
                j -= 1
            else:
                if i == -1:
                    i = 0
                    j = good_suffix[j]
                else:
                    i -= 1
        return good_suffix

    n = len(s)
    m = len(p)
    bad_char = build_bad_char_table(p)
    good_suffix = build_good_suffix_table(p)
    i = m - 1
    j = m - 1
    while i < n:
        if p[j] == s[i]:
            i -= 1
            j -= 1
        if j == -1:
            return i + 1
        elif i < n and p[j] != s[i]:
            if bad_char[ord(s[i])] != -1:
                i = i - 1 - bad_char[ord(s[i])]
                j = m - 1
            else:
                i = i - 1
                j = good_suffix[j]
    return -1

# 示例
s = "ABABDABACDABABCABAB"
p = "ABABCABAB"
print(boyer_moore_search(s, p))  # 输出：10

3. AC自动机

AC自动机（Aho-Corasick）是一种多模式字符串匹配算法，可以同时匹配多个模式串。

3.1 算法原理

AC自动机利用有限状态机（FSM）的思想，将多个模式串构建成一个自动机。在匹配过程中，自动机会在每个状态上存储所有到达该状态的模式串，从而实现多模式匹配。

3.2 代码实现

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

def build_trie(patterns):
    root = TrieNode()
    for pattern in patterns:
        node = root
        for char in pattern:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    return root

def ac_automaton_search(s, patterns):
    root = build_trie(patterns)
    i = 0
    while i < len(s):
        node = root
        while i < len(s) and s[i] in node.children:
            node = node.children[s[i]]
            i += 1
            if node.is_end_of_word:
                print(f"Pattern '{patterns[patterns.index(node.is_end_of_word)]}' found at index {i - len(patterns[patterns.index(node.is_end_of_word)])}")
        i += 1

# 示例
s = "ABABDABACDABABCABAB"
patterns = ["ABAB", "ABABCABAB", "CDAB"]
ac_automaton_search(s, patterns)

总结

掌握KMP、Boyer-Moore和AC自动机等字符串匹配算法，对于ACM竞赛来说至关重要。通过本文的介绍，相信你已经对这些算法有了更深入的了解。在竞赛中，灵活运用这些算法，相信你一定能够取得优异的成绩！

-- 展开阅读全文 --