News for hackers. Stuff that matters.
Re:New string search algorithm by bnoordhuis on Friday February 11, 2011 @07:50PM (#2208864)
The author states that preprocessing takes O(m) time but that is on average.

A quick review of the code makes me think that its worst case is actually on the order of O((s * (s + 1)) / 2), where s = m / 2.

The Achilles heel is the hash function. It's trivial to create collisions and have the insertion time for word w turn from O(1) to O(w).

Re:New string search algorithm by martincmartin on Friday February 11, 2011 @08:19PM (#2208930)
Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
Re:New string search algorithm by bnoordhuis on Friday February 11, 2011 @08:28PM (#2208956)
Sorry, I updated my comment just as you posted yours.

But - and I don't want to sound pedantic - how is m^2 not exponential growth?

Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.

Re:New string search algorithm by bigiain on Friday February 11, 2011 @08:43PM (#2208988)
Because 2^m and m^2 are very different...

Using terminology like "exponential" and "quadratic" correctly in a discussion of algorithms is not pedantic...

Re:New string search algorithm by Locke1689 on Friday February 11, 2011 @08:40PM (#2208984)
Exponential growth is O(2^m). This is not pedantic -- it's definition. O(m^k) is polynomial, O(k^m) is exponential.
Re:New string search algorithm by cperciva on Saturday February 12, 2011 @01:15AM (#2209463)
how is m^2 not exponential growth

m^2 is exponential -- in the value 2. But the value 2 doesn't change very rapidly, so we tend to focus on the m component of the expression. :-)

Re:New string search algorithm by state_machine on Friday February 11, 2011 @08:45PM (#2208993)
Because 2, the exponent in that expression, is a constant.

Exponential growth would be 2^m.

Re:New string search algorithm by theoretical on Friday February 11, 2011 @08:45PM (#2208992)
x^2 is quadratic, 2^x (for example) is exponential.

Have a look at http://en.wikipedia.org/wiki/Time_complexity , it's pretty comprehensive.

Re:New string search algorithm by lvvlvv on Saturday February 12, 2011 @01:33PM (#2210691)
I am the author. You are right. I've updated the page.
Re:New string search algorithm by leif on Saturday February 12, 2011 @12:48PM (#2210553)
Universal hashing will prevent collision problems.