0

私の問題:文字列があるとしましょう:

ali, aligator, aliance

それらには共通のプレフィックスがあるため、次のようにそれらをトライに保存したいと思います。

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

これまでのところ、Biopython ライブラリの trie 実装を使用できます。しかし、私が達成したいのは、特定の部分文字列を含むトライ内のすべてのキーを見つける能力です。

例えば：

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

助言がありますか？

4

2 に答える 2

1

編集：あなたは接尾辞木を探しているかもしれないと思います。特に「接尾辞木は、最も長い一般的な部分文字列の問題に対する最初の線形時間ソリューションの1つを提供した」ことに注意してください。

非常に関連していると思われる別のSOの質問に気づきました：Trieを使用して最長の一般的な部分文字列を見つける

于 2012-11-19T14:36:53.720 に答える
-3

私はこのようなことをします：

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']
于 2012-11-19T15:10:31.773 に答える