I know several basic string-matching algorithms such as KMP or Boyer-Moore, but all of those analyze the pattern before searching.However, if one has a single character, there is not much to analyze. So is there any better algorithm than the naive search of comparing every character of the text ?
It being understood that the worst case is
The naive method performs a character comparison and an end-of-text comparison for each character.
Using a sentinel (i.e. a copy of the target character at the end of the text) reduces the number of comparisons to 1 per character.
At the bit twiddling level there is:
to know if any byte in a word (
By ANDing these two sub-expressions (
Now we can XOR the value to test (
This is often used in a typical
(Stephen M Bennet suggested this on December 13, 2009. Further details in the well known Bit Twiddling Hacks).
The hack passes the brute force test (just be patient):
Thank you for the remark.
The answer was meant to be anything but an essay on multi-byte / variable-width encodings :-) (in all fairness that's not my area of expertise and I'm not sure it's what the OP was looking for).
Anyway it seems to me that the above ideas/tricks could somewhat be adapted to MBE (especially self-synchronizing encodings):
Any text search algorithm which searches for every occurence of a single character in a given text has to read each character of the text at least once, that should be obvious. And since this is sufficient for a one-time search, there can be no better algorithm (when thinking in terms of run time order, which is called "linear" or O(N) for this case, where N is the number of characters to search through).
However, for real implementations, there are surely lots of micro-optimizations possible, which do not change the run time order at a whole, but lower the actual run time. And if the goal is not to find every occurence of a single character, but only the first, you can stop at the first occurence, of course. Nevertheless, even for that case, the worst-case is still that the character you are looking for is the last character in the text, so the worst case run time order for this goal is still O(N).
If your "haystack" is searched more than once, a histogram based approach is going to be extremely fast. After the histogram is built, you only need a pointer lookup to find your answer.
If you only need to know whether the searched pattern is present, a simple counter can help. It can be extended to include the position(s) at which each character is found in the haystack, or the position of the first occurence.
If you need to search for characters in this very same string more than once, then a possible approach is to divide the string into smaller parts, possibly recursively, and to use bloom filters for each of these parts.
Since a bloom filter can tell you for sure if an character is not in the part of the string that's "represented" by the filter, you can skip some parts while searching for characters.
As example: For the following string one could split it into 4 parts (each 11 characters long), and fill for each part a bloom filter (perhaps 4 byte large) with the characters of that part:
You can speed up your search, e.g. for the character
Using a recursive, tree-like approach should get you near
In this configuration one needs (again, assuming we got lucky and didn't get a false positive from one of the filters) to check
to get to the final part (where one needs to check 3 characters until finding the
Using a good (better as the above) subdivision scheme you should get pretty nice results with that. (Note: Bloom filters at the root of the tree should be larger than close to the leaves, as shown in the example, to get a low false positives probability)
If the string is going to be searched multiple times (typical "search" problem), solution can be O(1). Solution is to build an index.
Map, where Key is the Character and Value is a list of indices for that character in the string.
With this, a single map lookup can provide the answer.