A Proof of the Correctness of Uratani's String Searching AIgorithm
Masayuki Takeda, 正幸 竹田 · QIR (Kyushu University Institutional Repository) (Kyushu University) · 1988
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 during 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.