如何实现输入字符串后缀与短语前缀匹配的检索功能？

嘿，这个需求我之前也碰到过，逐字符逐个比对确实在短语数量多的时候效率拉胯，给你几个更靠谱的优化方案，都是Python里能直接落地的：

如果你的短语列表是固定的，且查询次数很多，前缀树绝对是最优解。它能把所有短语的前缀结构存储起来，每次查询时只需要遍历输入字符串的后缀，就能快速定位到所有匹配的短语。

先实现一个简单的Trie结构：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.phrases = []  # 存储所有以当前路径为前缀的短语

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, phrase):
        node = self.root
        for char in phrase:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.phrases.append(phrase)  # 每个前缀节点都保存对应的短语
    
    def get_phrases_with_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return node.phrases.copy()

然后实现getNext函数：

def getNext(input_str, phrase_list, trie=None):
    # 初始化Trie（仅第一次调用时构建）
    if not trie:
        trie = Trie()
        for phrase in phrase_list:
            trie.insert(phrase)
    
    matched_phrases = set()
    # 遍历输入字符串的所有可能后缀，收集匹配短语
    for i in range(len(input_str)):
        suffix = input_str[i:]
        matched_phrases.update(trie.get_phrases_with_prefix(suffix))
    
    return list(matched_phrases)

这个方案的优势是预处理一次，后续查询极快，时间复杂度是O(L + M)（L是输入字符串长度，M是匹配到的短语数量），比逐字符比对的O(N*min(L,P))（N是短语数，P是短语平均长度）高效太多。

如果你的短语列表规模不大，直接用Python内置的startswith方法就足够简单高效，不用搞复杂的数据结构：

def getNext(input_str, phrase_list):
    matched_phrases = set()
    input_len = len(input_str)
    for phrase in phrase_list:
        max_match_len = min(input_len, len(phrase))
        # 检查短语的前缀是否是输入字符串的某个后缀
        for k in range(1, max_match_len + 1):
            if phrase[:k] == input_str[-k:]:
                matched_phrases.add(phrase)
                break  # 匹配到就停止检查，节省时间
    return list(matched_phrases)

这个方案实现简单，适合短语数量少的场景，虽然时间复杂度还是O(N*min(L,P))，但比纯逐字符比对要优化不少。

如果你的短语列表可以排序，用bisect模块做二分查找能大幅减少比对次数：

import bisect

def getNext(input_str, phrase_list):
    sorted_phrases = sorted(phrase_list)
    matched_phrases = set()
    input_len = len(input_str)
    
    for i in range(input_len):
        suffix = input_str[i:]
        # 找到第一个大于等于当前后缀的短语
        idx = bisect.bisect_left(sorted_phrases, suffix)
        # 遍历后续短语，直到前缀不匹配
        while idx < len(sorted_phrases):
            phrase = sorted_phrases[idx]
            if phrase.startswith(suffix):
                matched_phrases.add(phrase)
                idx += 1
            else:
                break
    return list(matched_phrases)

这个方案预处理是O(N log N)排序，每次查询的时间复杂度是O(L log N + M)，兼顾了实现复杂度和查询效率，适合中等规模的短语列表。

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