PricingLoginStart free
Competitive Programming Academy · レッスン

接頭辞検索のための Trie

単語の接頭辞を高速に保存・検索します

レッスン 4/413 ステップ

「接頭辞検索のための Trie」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

単語を賢く保存

トライは、共通するプレフィックスを共有しながら単語を保存する木構造です。プレフィックスに関する問い合わせを非常に高速に処理できます。🌳

単なる集合では不十分な理由

集合は単語全体の検索には使えますが、トライならプレフィックスに関する問い合わせにも対応できます。たとえば、preで始まる単語があるかを調べられます。

ノードとエッジ

各ノードはある単語内の位置を表し、各エッジにはルートからの経路上にある文字がラベルとして付いています。

子ノードを辞書で管理

Pythonでは、文字を子ノードに対応付けるdictをノードとして使うのが最も簡単です。すっきりしていて柔軟な方法です。

root = {}

単語の挿入

挿入するときは、文字を1つずつたどり、子ノードが存在しない場合は作成します。

node = root
for c in word:
    node = node.setdefault(c, {})

単語の終端を記録

挿入が終わったら終端フラグを設定し、それが単なるプレフィックスではなく単語全体であることを判別できるようにします。

node['#'] = True

単語全体の検索

検索では文字を順にたどります。途中で存在しない箇所があれば、その単語はありません。最後に終端フラグを確認します。

for c in word:
    if c not in node:
        return False
    node = node[c]

プレフィックスの確認

プレフィックスの問い合わせでは同じようにたどりますが、終端フラグの確認は省略します。最後のノードまで到達できれば存在します。

計算量

挿入と検索にかかるコストは、保存した単語数に関係なく、単語の長さO(L)です。重要なのは単語の長さです。

プレフィックスごとの単語数を数える

各ノードに個数を保存すると、指定したプレフィックスを共有する保存済み単語の数をすぐに求められます。

トライが役立つ場面

トライはオートコンプリート、辞書の検索、ビット列に対するXOR最大化問題などに利用できます。コンテストの文字列問題では定番のデータ構造です。

確認

トライでの検索に実際にはどれだけのコストがかかるか確認してください。

対話的なレッスンで答える

まとめ：トライの仕上げ

これでトライを構築し、O(L)で挿入と検索を行い、プレフィックスや個数に関する問い合わせにも高速に答えられるようになりました。🌟

無料で開始

AI チューターと学ぶ Python — 無料

ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。

コース
30
レッスン
120
無料で学習を始めるコース全体を表示

よくある質問

「接頭辞検索のための Trie」レッスンは無料ですか？

はい。「接頭辞検索のための Trie」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「接頭辞検索のための Trie」で何を学びますか？

単語の接頭辞を高速に保存・検索します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「接頭辞検索のための Trie」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. KMP の接頭辞関数
  2. 多項式文字列ハッシュ
  3. パターン検索の Z 関数
  4. 接頭辞検索のための Trie
← Competitive Programming Academyに戻る