Commentz-Walter algorithm

[2] GNU grep once implemented a string matching algorithm very similar to Commentz-Walter.

Comparing the Aho-Corasick to the Commentz-Walter Algorithm yields results with the idea of time complexity.

The reason for this lies in the fact that Commentz-Walter was developed by adding the shifts within the Boyer–Moore string-search algorithm to the Aho-Corasick, thus moving its complexity from linear to quadratic.

According to a study done in “The Journal of National Science Foundation of Sri Lanka 46” Commentz-Walter seems to be generally faster than the Aho–Corasick string matching algorithm.

However, the journal does state that there is no critical analysis on this statement and that there is a lack of general agreement on the performance of the algorithm.

[5] As seen in a visualization of the algorithm’s running time done in a study by “The International Journal of Advanced Computer Science and Information Technology” the performance of the algorithm increased linearly as the shortest pattern within the pattern set increased.