トリプル(Trie)

trieとは?

trayはCSのブラウズツリーです.文字列は通常キーです.
バイナリ・ナビゲーション・ツリーとは異なり、ツリー内の任意のノードは、そのノード自体に関連する鍵を保存しません.
逆に、ノードはツリー内の位置で関連するキーを定義します.
すなわち,キー値は資料構造全体に分散する.ノードのすべてのサブノードは、ノードに関連付けられた文字列の共通接頭辞を共有します.
ルート(head)は空の文字列に関連付けられています.
一部の内部ノードは鍵に対応する可能性があるが、通常、鍵を端末に関連付ける傾向がある.したがって、すべてのノードが鍵に関連付けられているわけではありません.

検索文字列に効率的です。

3つの例
各文字列のアルファベットはノードの値になります.
一部のノードにはwordの要素に関する情報が含まれています.これは、ノードにナビゲートすると、ナビゲーション中にアルファベットからなる単語が現在のtrieに存在することを意味します.
例えば、「韓国」では、「a」だけが「韓国」の情報を持っている.
「korean」には「n」に「korean」という情報があります.
これにより,Trightは接頭辞が重複する単語を効率的に管理することができ,ある単語を検索するクエリでは,時間的複雑度はO(N)O(N)O(N)(N=単語の長さを検索する)ことによって見つけることができる.
時間の複雑なグラフィックでは優れていますが、各アルファベット、各順序に作成するノードがたくさんあるので、メモリが消費されます.

質問する

14425号:文字列セット

概要

実際には、上記の問題もハッシュによって解決することができる.
しかし、メモリ制限が1536 MBであることを考慮すると、フラッシュの練習には良い問題だと思います.

3階層アーキテクチャ

ノードクラス

class Node:
	def __init__(self, key, data=None):
		self.key = key
		self.data = data
		self.children = {}

trieのコンポーネントノードに関するクラスです.
key(アルファベット)、data(単語は存在しない)、children(現在のノードのサブノード)から構成されます.
dataにより,現在のノードのkeyを最後のスペルとする単語があるか否かを判断できる.
childrenは、Trieクラスメソッドでノードを再帰的にナビゲートするために使用される.

Trueクラス

class Trie:
	def __init__(self):
		self.head = Node(None)

triclassの作成者はkey=Noneノードです.
そしてこのノードはTreeのhead,すなわちルートノードとなる.

insert

def insert(self, word):
		cur_node = self.head
		for char in word:
			if char not in cur_node.children:
				cur_node.children[char] = Node(char)
			cur_node = cur_node.children[char]
		cur_node.data = word

trieに単語を挿入する方法.
wordをparameterとして受け入れ,wordのスペルをノードオブジェクトごとに生成しtrieに入れる.
trieを入れることはheadからサブノード(children)に順次割り当てることを意味する.

search

def search(self, word):
		cur_node = self.head
		for char in word:
			if char in cur_node.children:
				cur_node = cur_node.children[char]
			else:
				return False

検索する単語がtrieに存在するかどうかを確認する方法.
ここにいるよデータを使用します.
ヘッダーから順にサブノードをチェックし、スペルが一致するノードがある場合は、同じ検索を再帰的に繰り返す.
スペルがtrieにない場合、またはすべてのスペルがtrieにあり、データがない場合はfalseを返します.

start_with

def start_with(self, prefix):
		cur_node = self.head

		for char in prefix:
			if char in cur_node.children:
				cur_node = cur_node.children[char]
			else:
				return None

		words = []
		next_node = []
		if cur_node.data: #app
			words.append(cur_node.data)
		next_node.extend(list(cur_node.children.values()))
		if len(next_node) == 0: return words

		cur_node = list(next_node)
		next_node = []
		while True:
			for node in cur_node:
				if node.data:
					words.append(node.data)
				next_node.extend(list(node.children.values()))
			if len(next_node) == 0: return words
			cur_node = list(next_node)
			next_node = []

検索する文字列を接頭辞として使用する単語をすべて返す方法.
headからchildをチェックし、prefixのアルファベット全体がtrieに存在するかどうかを決定します.
存在しない場合はNoneを返します.
prefixの最後のアルファベットの後にすべてのchildをナビゲートし、ノードにデータがあることを確認する必要があります.
単語はwordsに追加され,現在のノードのサブノードをnext nodeに保存し,cur nodeをnext nodeに更新する.その後更新されるcur nodeについても同じ操作を繰り返します.
動作実行方式はBFSと同様である.
まずすべてのchildをチェックし、次のwhile文で作業します.
cur nodeが更新されない場合は、保存したwordを返します.

質問回答コード

import sys

In = lambda: sys.stdin.readline().rstrip()
MIS = lambda: map(int, In().split())

class Node:
	def __init__(self, key, data=None):
		self.key = key
		self.data = data
		self.children = {}

class Trie:
	def __init__(self):
		self.head = Node(None)

	def insert(self, word):
		cur_node = self.head
		for char in word:
			if char not in cur_node.children:
				cur_node.children[char] = Node(char)
			cur_node = cur_node.children[char]
		cur_node.data = word

	def search(self, word):
		cur_node = self.head
		for char in word:
			if char in cur_node.children:
				cur_node = cur_node.children[char]
			else:
				return False

		if cur_node.data:
			return True
		else:
			return False

	def start_with(self, prefix):
		cur_node = self.head

		for char in prefix:
			if char in cur_node.children:
				cur_node = cur_node.children[char]
			else:
				return None

		words = []
		next_node = []
		if cur_node.data: #app
			words.append(cur_node.data)
		next_node.extend(list(cur_node.children.values()))
		if len(next_node) == 0: return words

		cur_node = list(next_node)
		next_node = []
		while True:
			for node in cur_node:
				if node.data:
					words.append(node.data)
				next_node.extend(list(node.children.values()))
			if len(next_node) == 0: return words
			cur_node = list(next_node)
			next_node = []

if __name__ == "__main__":
	N, M = MIS()
	trie = Trie()
	for _ in range(N):
		trie.insert(In())

	ans = 0
	for _ in range(M):
		if trie.search(In()):
			ans += 1
	print(ans)