47 ms·
As I understand this, the KMP function uses an optimal algorithm, while the indexOf version uses a suboptimal algorithm but takes advantage of a native (C) impl
by glenjamin 16y ago
As I understand this, the KMP function uses an optimal algorithm, while the indexOf version uses a suboptimal algorithm but takes advantage of a native (C) implementation found in the standard library.
It follows that the fastest approach should be to implement the KMP algorithm natively, using Pyrex rather than C should make this fairly trivial.
- cracki 16y agobesides Pyrex, there's also Cython (I don't know if one superseeded the other or what exactly their relationship is)
- wisty 16y agoPyrex is the original. Cython is the fork by people who wanted to add more features. I think their relationship is reasonable, but not reasonable enough for the two projects to link to each-other.
- endtime 16y ago>It follows that the fastest approach should be to implement the KMP algorithm natively Not exactly - well, depends what you mean by "fastest". The KMP algorithm is optimal in the worst case, not necessarily in the average case. If you implemented KMP in C and then fed it typical rather than pathological strings, you might still do better with the indexOf algorithm.