Trie木
投稿者：CarpDay.icon
1. Trie木の概要
「トライ」や「Suffix Tree」とも呼ばれる．
参考：https://ja.wikipedia.org/wiki/トライ_(データ構造)
2. 作成コード（Python）
参照元：ABC353Eの解説
code: python
s = input().split()
tree = {}
for t in s:
current = tree
for c in t:
if c in current:
currentc0 += 1
else:
currentc = 1, {}
current = currentc1
print(tree)
入力例
code: txt
ab bb aaa bba baba babb aaaba aabbb a a b
出力
code: txt
{'a': [6, {'b': 1, {}, 'a': [3, {'a': [2, {'b': [1, {'a': 1, {}}]}], 'b': [1, {'b': [1, {'b': 1, {}}]}]}]}], 'b': [5, {'b': [2, {'a': 1, {}}], 'a': [2, {'b': [2, {'a': 1, {}, 'b': 1, {}}]}]}]}
分かりやすくするために改行を追加
code: txt
{'a': [6, { # 'a*' 6個(ab, aaa, aaaba, aabbb, a, a)
'b': 1, {}, # 'ab*' 1個(ab)
'a': [3, { # 'aa*' 3個(aaa, aaaba, aabbb)
'a': [2, { # 'aaa*' 2個(aaa, aaaba)
'b': [1, { # 'aaab*' 1個(aaaba)
'a': 1, {}}]}], # 'aaaba*' 1個(aaaba)
'b': [1, { # 'aab*' 1個(aabbb)
'b': [1, { # 'aabb*' 1個(aabbb)
'b': 1, {}}]}]}]}], # 'aabbb*' 1個(aabbb)
'b': [5, { # 'b*' 5個(bb, bba, baba, babb, b)
'b': [2, { # 'bb*' 2個(bb, bba)
'a': 1, {}}], # 'bba*' 1個(bba)
'a': [2, { # 'ba*' 2個(baba, babb)
'b': [2, { # 'bab*' 2個(baba, babb)
'a': 1, {}, # 'baba*' 1個(baba)
'b': 1, {}}]}]}]} # 'babb*' 1個(babb)
3. Trie木の利用
DFS/BFSで検索を行う．
#木 #グラフ理論 #BFS/DFS