文字列探索

アルゴリズム探索アルゴリズム

文字列探索 (もじれつたんさく) とは?

 状態:終了後再開  閲覧数:1,816  投稿日:2016-11-09  更新日:2018-03-11  
「ある文字列」の中から、別の「ある文字列」を探索すること
・「テキスト(文字列)S」から「単語Wで指定されたパターン」が出現する場所を見つける操作
・「文字の並び」が重要

文字列とは?
・「ある定まった文字集合の要素」を任意に並べた系列のこと

パターン
・「探したい文字の並び」のこと
・単語
・W

テキスト
・「検索される文字列」のこと
・S

各種アルゴリズム


Morris-Pratt algorithm
クヌース–モリス–プラット法
ボイヤー-ムーア法
Quick Search法 ボイヤー-ムーア法の亜種の一つで、さまざまな亜種のうちもっとも簡単で、かつ高速。
エイホ-コラシック法
ラビン-カープ法
Bitapアルゴリズム(shift-and, shift-orなどでも知られる)
Bit-parallel手法



・終了後→探索アルゴリズム


リスト探索(list search)アルゴリズム

クヌース–モリス–プラット法

コメント投稿(ログインが必要)