<学術雑誌論文>
A FAST MATCHING ALGORITHM FOR PATTERNS WITH PICTURES

作成者
本文言語
出版者
発行日
収録物名
開始ページ
終了ページ
出版タイプ
アクセス権
Crossref DOI
概要 The pattern matching problem is to find all occurrences of patterns in a text string. An extended problem is considered for patterns with pictures, where a picture is a don't-care that matches only th...e symbols in the set it represents. For example, let $ A $ be a picture $ a, b, ldots , z $, and $ N $ for $ 0, 1, ldots , 9 $. Then, $ mathrm{ab}NN $, $ mathrm{a7}NNNNA, ldots $ are patterns. For multiple string patterns, the Aho-Corasick algorithm, which uses a finite state pattern matching machine, is widely known to be quite efficient. A fast matching algorithm for multiple patterns with pictures is presented as a natural extension of the AC algorithm. A pattern matching machine can be built easily, and then it runs in linear time proportional to the text length as the AC algorithm achieves. Moreover, a correctness proof of the algorithm is given.続きを見る

本文情報を非表示

p137 pdf 800 KB 99  

詳細

PISSN
NCID
レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2020.05.01

この資料を見た人はこんな資料も見ています