Do we need a more generic sequence searching algorithm?

Dear list,

I have recently implemented a generic sequence searching template
function, named single_pass_search, which is more generic than
std::search and has better worst case complexity at the same time.

More specifically, the main advantage of the single_pass_search over
the std::search is its capability to search for a sub-sequence in a
search-range that is accessed through a pair of single-pass (input)
iterators, while std::search requires that the search-range must be
accessed via forward iterators at least. This practically means that
single_pass_search can for example search a file directly through a
pair of istream iterators, without requiring the interference of an
intermediate container. (Please see "http://www.codeproject.com/KB/stl/
single_pass_search.aspx" for more.)

Although, I believe that single_pass_search can probably be
interesting in theory, I still have some doubts regarding its
practical usefulness to the average C++ developer. Hence, I would be
really grateful to anyone that will express his opinion regarding the
single_pass_search usefulness. Please don't try to be nice to me, I
need real feedback, however some reasoning together with your opinion
would be very welcomed.

Thank you very much,
Jim Xochellis

re: Do we need a more generic sequence searching algorithm?

I have recently implemented a generic sequence searching templateNo internal storage requirements for buffering and no backtracking at
all!
single_pass_search is using good-suffix shifting, instead of
buffering,
for better performance. This is why its complexity is also improved.
It only needs a small lookup table for the good-suffix shifting.

Thank you,
-Jim

re: Do we need a more generic sequence searching algorithm?

Do you mean you have a general search algorithm in o(n) complexitySorry, I need no backtracking, but I still need a small lookup-table,
(see previous e-mail) which has to be constructed in a pre-processing
phase. The internal algorithm is actually a KMP amelioration. (Which
is based on the good-suffix shifting technique.)

References:
"http://www.codeproject.com/KB/stl/single_pass_search.aspx"
"http://www.cs.rpi.edu/~musser/gp/gensearch1.pdf"

-Jim