C#中如何高效检查字符串是否以指定列表中的前缀开头？

场景说明 #

需要判断输入字符串是否以给定列表中的任意字符串作为前缀，比如前缀列表为["1234", "1235", "1236"]时，"1235av2425"返回true，"1237352ko"返回false。下面分两种场景给出高效实现方案：

方案一：直接遍历（适合小规模前缀列表） #

如果前缀列表数量不多（几十条以内），直接遍历每个前缀并调用字符串的startswith方法是最简单高效的方式，代码直观，性能足够。

以Python为例：

def has_matching_prefix(input_str, possible_prefixes):
    for prefix in possible_prefixes:
        if input_str.startswith(prefix):
            return True
    return False

# 测试示例
possible_prefixes = ["1234", "1235", "1236"]
print(has_matching_prefix("1235av2425", possible_prefixes))  # 输出 True
print(has_matching_prefix("1237352ko", possible_prefixes))   # 输出 False

时间复杂度：O(n*m)，其中n是前缀列表长度，m是前缀平均长度。小列表场景下，该开销可忽略。

方案二：前缀树（Trie）实现（适合大规模前缀列表） #

如果前缀列表规模较大（上百条及以上），逐个遍历的效率会下降，这时可以用前缀树优化。前缀树会合并所有前缀的公共部分，检查时只需沿输入字符串的字符逐个匹配，一旦不匹配就提前终止，单次检查时间复杂度仅为O(k)（k是输入字符串长度）。

以Python为例实现前缀树：

class TrieNode:
    def __init__(self):
        self.children = {}  # 子节点映射：字符 -> TrieNode
        self.is_end = False  # 标记当前节点是否为某个前缀的结尾

def build_prefix_trie(prefixes):
    root = TrieNode()
    for prefix in prefixes:
        current_node = root
        for char in prefix:
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_end = True
    return root

def check_prefix_with_trie(input_str, trie_root):
    current_node = trie_root
    for char in input_str:
        # 当前节点已是前缀结尾，直接返回True
        if current_node.is_end:
            return True
        # 字符不匹配，提前终止检查
        if char not in current_node.children:
            break
        current_node = current_node.children[char]
    # 检查遍历终点是否为前缀结尾（比如输入字符串刚好等于某前缀）
    return current_node.is_end

# 测试示例
possible_prefixes = ["1234", "1235", "1236"]
trie_root = build_prefix_trie(possible_prefixes)
print(check_prefix_with_trie("1235av2425", trie_root))  # 输出 True
print(check_prefix_with_trie("1237352ko", trie_root))   # 输出 False

优势：前缀树只需构建一次，后续每次检查效率极高，尤其适合频繁进行前缀校验的场景。

补充：多模式匹配算法 #

如果不想自行实现前缀树，也可以使用成熟的多模式匹配算法（比如Aho-Corasick），多数编程语言都有对应的内置或第三方库支持，这类算法在处理大量前缀匹配时性能表现更优。

内容的提问来源于stack exchange，提问作者Bhav