Start Submission Become a Reviewer

Reading: Average time complexity analysis of Commentz-Walter algorithm


A- A+
Alt. Display

Research Articles

Average time complexity analysis of Commentz-Walter algorithm


SD Dewasurendra,

University of Peradeniya, LK
About SD

Department of Computer Engineering


X close

SM Vidanagamachchi

University of Ruhuna, LK
About SM

Department of Computer Science


X close


The Commentz-Walter algorithm provides a suffix-based, exact multiple string matching procedure that combines the ideas of both Aho-Corasick and Boyer-Moore string matching algorithms. Aho-Corasick algorithm is known as the fastest exact multiple string matching algorithm with linear worst case time complexity, and Boyer-Moore algorithm utilises a shift based approach in handling mismatches in the matching phase to obtain a usually sub linear time complexity. Due to the complexity of the Commentz-Walter algorithm, a systematic and a comprehensive time complexity analysis has not yet been reported in the literature. In this article, a comprehensive average time complexity analysis of Commentz Walter algorithm is presented and it is used to formally explain empirical results reported elsewhere for exact and limited tolerance string matching. Performance analysis model permits ‘complete’ exploration of the solution space of Commentz-Walter with respect to all relevant parameters. The models developed here could be useful for other researchers to investigate the appropriateness of Commentz-Walter to specific application domains. The analysis method can be extended to cover Aho-Corasick and other string matching algorithms without much difficulty.

How to Cite: Dewasurendra, S. and Vidanagamachchi, S., 2018. Average time complexity analysis of Commentz-Walter algorithm. Journal of the National Science Foundation of Sri Lanka, 46(4), pp.547–557. DOI:
Published on 31 Dec 2018.
Peer Reviewed


  • PDF (EN)

    comments powered by Disqus