P7537 [COCI2016-2017#4] Rima（トライ木と木上の動的計画法）
P7537 [COCI2016-2017#4] Rima
トライ木と木上の動的計画法
問題の制約を整理すると、文字列の末尾に文字を追加したり、置換したり、削除したりできることが分かります。この操作は、あるポイントで削除が起こり、その後追加が続くため、単峰性を持ちます。両端の処理は対称なので、片側だけ考えれば十分です。文字列を逆転させてトライ木に挿入し、木上のDPで各ノードの部 ...
9月15日 19:50 投稿
トライ木（Trie木）の基礎と応用
基本概念
トライ木（Trie木）は文字列に関連するデータ構造で、辞書木または接頭辞木とも呼ばれます。その主な思想は「空間で時間を換える」ことです。大量の文字列を統計、ソート、または保存するために使用できます。検索する文字列をsとすると、トライ木の単一クエリの複雑度はO(|s|)です。
01トライ木は、XOR関連問題を扱うデータ構造のバリエーションです。複数の数 ...
8月3日 03:10 投稿
トライ木：効率的な文字列検索と接頭辞マッチングのためのデータ構造
トライ木（Trie）は、辞書木や接頭辞木とも呼ばれるデータ構造で、特定の文字列が存在するかどうかの検索や、特定の接頭辞を持つ文字列の数を効率的に数えるために使用されます。
トライ木は接頭辞の概念を利用しており、各文字列を一文字ずつ分解して木構造のノードに格納します。例えば、"cup", "apple", "cake", "app", "blog" という単語がある場合、以下のような木構 ...
5月19日 06:24 投稿