基于Trie树获取最长公共子串的实现求助

要通过你现有的Trie树实现最长公共子串，核心思路是将其中一个字符串的所有后缀插入Trie，再遍历另一个字符串的所有后缀，在Trie中查找最长的匹配前缀——这个匹配前缀就是两个字符串的公共子串，记录长度最大的即可。

步骤说明 #

• 插入第一个字符串的所有后缀：子串本质是某个后缀的前缀，把所有后缀插入Trie后，Trie就包含了第一个字符串的所有可能子串。
• 遍历第二个字符串的所有后缀：对每个后缀，在Trie中逐步匹配字符，直到无法匹配为止，记录此时的匹配长度和对应子串，最终保留最长的那个。

代码调整与实现 #

首先对你的Trie类做小修改，新增一个方法用于获取某个字符串在Trie中的最长匹配前缀长度：

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 对应a-z，原代码的27为冗余设置，此处修正
        self.isLeaf = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current = self.root 
        for letter in word:
            index = ord(letter) - ord('a')
            if not current.children[index]:
                current.children[index] = TrieNode()
            current = current.children[index]
        current.isLeaf = True

    def search(self, word: str) -> bool:
        current = self.root 
        for letter in word:
            index = ord(letter) - ord('a')
            if not current.children[index]:
                return False 
            current = current.children[index]
        return current.isLeaf

    def startsWith(self, prefix: str) -> bool:
        current = self.root 
        for letter in prefix:
            index = ord(letter) - ord('a')
            if not current.children[index]:
                return False
            current = current.children[index]
        return True

    # 新增方法：获取字符串s在Trie中的最长匹配前缀长度
    def get_longest_match_length(self, s: str) -> int:
        current = self.root
        max_len = 0
        for i, letter in enumerate(s):
            index = ord(letter) - ord('a')
            if not current.children[index]:
                break
            current = current.children[index]
            max_len = i + 1
        return max_len

然后实现最长公共子串的求解函数：

def longest_common_substring(s1: str, s2: str) -> str:
    trie = Trie()
    # 插入s1的所有后缀
    for i in range(len(s1)):
        trie.insert(s1[i:])
    
    max_len = 0
    result = ""
    # 遍历s2的所有后缀，找最长匹配
    for i in range(len(s2)):
        current_len = trie.get_longest_match_length(s2[i:])
        if current_len > max_len:
            max_len = current_len
            result = s2[i:i+max_len]
    
    return result

测试示例 #

s1 = "abcde"
s2 = "abxde"
print(longest_common_substring(s1, s2))  # 输出: "ab"

关键逻辑解释 #

• 插入所有后缀：比如s1 = "abc"，插入的后缀是"abc"、"bc"、"c"，这样Trie中包含了"a"、"ab"、"abc"、"b"、"bc"、"c"等所有子串。
• 遍历s2的后缀：比如s2 = "abx"，后缀是"abx"、"bx"、"x"，对每个后缀在Trie中匹配，最长的匹配前缀就是"ab"，也就是两个字符串的最长公共子串。

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