C++4字符违禁词查找算法故障排查求助

核心错误原因 #

你的方案存在两个致命问题，导致无法定位目标违禁词：

• 跨边界干扰判断：直接拼接4字符单词时，前一个单词的末尾字符会和后一个单词的开头字符组成新的4字符组合，这些组合会干扰sendMessage()的判断——比如返回true可能是因为跨边界组合，而非目标违禁词；缩小范围拆分时，又会把这个跨边界组合拆开，导致返回false，丢失目标。
• 二分拆分逻辑错误：按字符位置拆分大字符串，可能把完整的4字符单词拆成两半，或者保留无效的跨边界片段，导致判断结果完全失真。

修正方案 #

1. 拼接时添加分隔符 #

在每个4字符单词之间插入非小写字母的分隔符（比如#），确保所有可能的4字符候选只有原本的单词，不会出现跨单词的无效组合。这样sendMessage()返回true时，必然是某一个完整的4字符单词为违禁词。

2. 按单词数量而非字符位置二分 #

二分法的拆分单位是单词组，而非字符位置。比如初始2500个单词，第一次拆成前1250个和后1250个，分别拼接（带分隔符）后调用sendMessage()，定位到包含违禁词的组，再继续拆分，直到缩小到单个单词。

修正后的代码示例 #

def find_forbidden_word(word_list, sendMessage):
    candidates = word_list.copy()
    
    while len(candidates) > 1:
        mid = len(candidates) // 2
        # 拼接前半组，单词间用#分隔
        left_str = '#'.join(candidates[:mid])
        if sendMessage(left_str):
            candidates = candidates[:mid]
        else:
            # 拼接后半组
            right_str = '#'.join(candidates[mid:])
            if sendMessage(right_str):
                candidates = candidates[mid:]
            else:
                # 理论上不会走到这里，初始调用已确认存在违禁词
                return None
    # 验证最后剩下的单个单词
    return candidates[0] if sendMessage(candidates[0]) else None

# 测试用例
def mock_sendMessage(s):
    return "abcd" in s

word_list = [chr(ord('a')+i)*4 for i in range(2500)]
word_list[1234] = "abcd"  # 插入测试违禁词
print(find_forbidden_word(word_list, mock_sendMessage))  # 输出abcd

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