## ＜学術雑誌論文＞A FAST MATCHING ALGORITHM FOR PATTERNS WITH PICTURES

作成者 著者識別子 作成者名 所属機関 所属機関名 Department of Information Systems, Interｄisciplinary Graduate School of Engineering Science, Kyushu University 九州大学大学院総合理工学研究科情報システム学専攻 英語 Research Association of Statistical Sciences 統計科学研究会 1993-03 25 3/4 137 153 Version of Record open access https://doi.org/10.5109/13427 Bulletin of informatics and cybernetics || 25(3/4) || p137-153 http://bic.math.kyushu-u.ac.jp/ Bulletin of informatics and cybernetics || 25(3/4) || p137-153 http://bic.math.kyushu-u.ac.jp/ Bulletin of informatics and cybernetics || 25(3/4) || p137-153 http://bic.math.kyushu-u.ac.jp/ 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 348

### 詳細

PISSN 0286-522X 2435-743X AA10634475 13427 査読有 学術雑誌論文 2009.04.22 2020.10.22