著者

市川 龍治 山本 博章

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.708, pp.41-48, 2002-03-05

---

本論文では,拡張正則表現に対する文字列照合問題を扱う。すなわち,長さmの拡張正則表現rと長さnのテキストxが与えられたとき,xの中にrと一致する文字列が存在するかどうか判定する問題である。山本の認識アルゴリズムを利用することによってこの問題を簡単にO(mn^2 +kn^3)時間かつO(mn+kn^2)領域で解くことができる。ここでは,このアルゴリズムを非決定性有限オートマトンおよび決定性有限オートマトンを使って実装することにより,その効率さについて実験的に評価する。