ra*****@yahoo.com (rakesh) wrote in message news:<d9**************************@posting.google. com>...
Hi,
I have a requirement in which I need to search a string in a file
stored on a harddisk. String which needs to be searched would be
stored in a file with delimiter as new line character. some of the
ways of doing this are
1. Read each line and do string compare immediately.
This is basically an O(N) algorithm.
2. Read each line, add each string into a stl vector and search for
the given string using stl bineary_search algorithm.
For binary_search to be meaningful, the items in the vector would
first have to be sorted. The sort (by itself) is slower than the
first search.
The second method makes sense if and only if you can read and sort the
data once, and then do multiple searches on the data. In that case,
the initial read/sort step is still O(N * log N), but each subsequent
search is O(log N), whereas in the first case, each search is O(N).
For string searching, I prefer Sunday's variant of
Boyer-Moore-Horspool string searching. Assuming the string you're
searching for is long and low in repitition, it can be quite fast.
OTOH, this is often overkill -- in a reasonably typical situation, the
real bottleneck will be in the I/O.
--
Later,
Jerry.
The universe is a figment of its own imagination.