エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Suffix Tree のお話 (その 1) - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Suffix Tree のお話 (その 1) - Qiita
まえがき この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。... まえがき この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。) 概要 列 $S$ の先頭から $0$ 個以上の要素を取り除いてできる列を、列 $S$ のSuffix (接尾辞) と呼びます。$S$ の Suffix は空列を含めて $|S| + 1$ 種類存在します。 $S$ の Suffix を全て格納した Trie 木を $S$ の Suffix Trie と呼びます。以下は $S = \mathrm{nknnknnnk}$ の Suffix Trie です。 Suffix Trie には長さ $O(|S|)$ の列が $S+1$ 個格納されるので、単にメモリだけでも $O(|S|^{2})$ のサイズが必要