Talk:Commentz-Walter algorithm

Asymptotic Runtime

Watson's thesis (referenced), Algorithm 4.18 is given as a generalized precursor to CW, and remark 4.20 gives its runtime as O(S*P) for text length S and max pattern length P. The final derivation of CW (Section 4.4.5) does not give a runtime. Section 13.1 claims "All of the algorithms [including CW-NORM, normal Commentz-Walter]... have worst-case running time linear in the length of the input string. ...the running time of... CW-NORM depends (linearly...) upon the length of the shortest keyword in the keyword set." Additionally, in Section 5.1: "Although the Knuth-Morris-Pratt and Aho-Corasick algorithms have better worst-case running time than the Boyer-Moore and Commentz-Walter algorithms (respectively), the latter two algorithms are known to be extremely efficient in practice." — Preceding unsigned comment added by Doctor J (talk • contribs) 22:27, 15 February 2012 (UTC)

We are editing this page as part of a university assignment, these are our usernames: - azarzosa - LeafThief - birdybutt — Preceding unsigned comment added by Azarzosa (talk • contribs) 23:18, 3 May 2022 (UTC)