python - python trie实现与子字符串匹配

Question

我的问题：假设我有字符串：

ali, aligator, aliance

因为它们有共同的前缀，所以我想将它们存储在 trie 中，例如：

trie['ali'] = None
trie['aligator'] = None
trie['aliance'] = None

到目前为止一切顺利——我可以使用 Biopython 库中的 trie 实现。但是我想要实现的是能够在该 trie 中找到包含特定子字符串的所有键。

例如：

trie['ga'] would return 'aligator' and 
trie['li'] would return ('ali','aligator','aliance').

有什么建议么？

Answer 1

编辑：我认为您可能正在寻找Suffix tree，特别注意到“后缀树还为最长的公共子字符串问题提供了第一个线性时间解决方案。”。

刚刚注意到另一个似乎非常相关的 SO 问题：使用 Trie 查找最长的公共子字符串

Answer 2

我会做这样的事情：

class Trie(object):
    def __init__(self,strings=None):
        #set the inicial strings, if passed
        if strings:
            self.strings = strings
        else:
            self.strings =[]

    def __getitem__(self, item):
        #search for the partial string on the string list
        for s in self.strings:
            if item in s:
                yield s

    def __len__(self):
        #just for fun
        return len(self.strings)

    def append(self,*args):
        #append args to existing strings
        for item in args:
            if item not in self.strings:
                self.strings.append(item)

然后：

t1 = Trie()
t1.append("ali","aligator","aliance")
print list(t1['ga'])
print list(t1['li'])
>>['aligator']
>>['ali', 'aligator', 'aliance']