<テクニカルレポート>
A Proof of the Correctness of Uratani's String Searching AIgorithm

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 The string searching problem is to find all occurrences of tile pattern(s) in a test string. The Aho-Corasick string searching algorithm finds simultaneously all occurrences of the multiple patterns d...uring one pass through the test. on the other hand, the Boyer-Moore algorithm is understood to be the fastest algorithm for a single pattern. By combining the ideas of these two algprithms, Uratani presented an efficierit string searching algpritnm for multiple patterns. The algorithm runs in sublinear time on the average as the BM algorithm achieves, and its preprocessing time is linear proportional to the sum of the length has the patterns like the AC algorithm. However, the correctness of the algorithm has not been discussed. In this paper. we prove the correctness of the algorithm.続きを見る

本文情報を非表示

rifis-tr-7 pdf 1.56 MB 130  

詳細

レコードID
査読有無
関連情報
主題
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20