Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|improve this question
12  
You can throw SIMD instructions at it, but you won't get anything better than O(n). – CodesInChaos Mar 19 at 12:58
6  
For a single search or multiple searches in the same string ? – Christophe Mar 19 at 18:27
    
KMP is definitely not something I would call a "basic" string-matching algorithm... I'm not even sure it's such a fast either, but it's historically important. If you want something basic try the Z algorithm. – Mehrdad Mar 19 at 20:39
    
Suppose there was a character position the search algorithm didn't look at. Then it wouldn't be able to distinguish between strings with the needle character in that position, and strings with a different character in that position. – immibis Mar 19 at 22:00

It being understood that the worst case is O(N), there are some very nice micro-optimizations.

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:

#define haszero(v)      ( ((v) - 0x01010101UL) & ~(v) & 0x80808080UL )
#define hasvalue(x, n)  ( haszero((x) ^ (~0UL / 255 * (n))) )

to know if any byte in a word (x) has a specific value (n).

The subexpression v - 0x01010101UL, evaluates to a high bit set in any byte whenever the corresponding byte in v is zero or greater than 0x80.

The sub-expression ~v & 0x80808080UL evaluates to high bits set in bytes where the byte of v doesn't have its high bit set (so the byte was less than 0x80).

By ANDing these two sub-expressions (haszero) the result is the high bits set where the bytes in v were zero, since the high bits set due to a value greater than 0x80 in the first sub-expression are masked off by the second (April 27, 1987 by Alan Mycroft).

Now we can XOR the value to test (x) with a word that has been filled with the byte value in which we're interested (n). Because XORing a value with itself results in a zero byte and nonzero otherwise, we can pass the result to haszero.

This is often used in a typical strchr implementation.

(Stephen M Bennet suggested this on December 13, 2009. Further details in the well known Bit Twiddling Hacks).


PS

this code is broken for any combination of 1111's next to a 0

The hack passes the brute force test (just be patient):

#include <iostream>
#include <limits>

bool haszero(std::uint32_t v)
{
  return (v - std::uint32_t(0x01010101)) & ~v & std::uint32_t(0x80808080);
}

bool hasvalue(std::uint32_t x, unsigned char n)
{
  return haszero(x ^ (~std::uint32_t(0) / 255 * n));
}

bool hasvalue_slow(std::uint32_t x, unsigned char n)
{
  for (unsigned i(0); i < 32; i += 8)
    if (((x >> i) & 0xFF) == n)
      return true;

  return false;
}

int main()
{
  const std::uint64_t stop(std::numeric_limits<std::uint32_t>::max());

  for (unsigned c(0); c < 256; ++c)
  {
    std::cout << "Testing " << c << std::endl;

    for (std::uint64_t w(0); w != stop; ++w)
    {
      if (w && w % 100000000 == 0)
        std::cout << w * 100 / stop << "%\r" << std::flush;

      const bool h(hasvalue(w, c));
      const bool hs(hasvalue_slow(w, c));

      if (h != hs)
        std::cerr << "hasvalue(" << w << ',' << c << ") is " << h << '\n';
    }
  }

  return 0;
}

Lots of upvotes for an answer which makes the assumption one chararacter=one byte, which is nowadays not the standard any more

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):

  • as noted in Johan's comment the hack can 'easily' be extended to work for double bytes or anything (of course you cannot stretch it too much);
  • a typical function that locates a character in a multibyte character string:
  • the sentinel technique can be used with a little foresight.
share|improve this answer
1  
This is a poor man's version of SIMD operation. – Ruslan Mar 19 at 13:58
    
@Ruslan Absolutely! This is often the case for effective bit twiddling hacks. – manlio Mar 19 at 14:39
2  
Nice answer. From a readability aspect, I don't understand why you write 0x01010101UL in one line and ~0UL / 255 in the next. It gives the impression that they must be different values, since otherwise, why write it in two different ways? – hvd Mar 19 at 19:08
3  
This is cool because it checks 4 bytes at once, but it requires multiple (8?) instructions, since the #defines would expand to ( (((x) ^ (0x01010101UL * (n)))) - 0x01010101UL) & ~((x) ^ (0x01010101UL * (n)))) & 0x80808080UL ). Wouldn't the single-byte comparison be faster? – Jed Schaaf Mar 19 at 22:36
1  
@DocBrown, the code can easily be made to work for double bytes (i.e. halfwords) or nibbles or anything. (taking into account the caveat I mentioned). – Johan Mar 20 at 10:56

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).

share|improve this answer

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.

string haystack = "agtuhvrth";
array<int, 256> histogram{0};
for(character: haystack)
     ++histogram[character];

if(histogram['a'])
    // a belongs to haystack
share|improve this answer

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:

The quick brown fox jumps over the lazy dog 
          |          |          |          |

You can speed up your search, e.g. for the character a: Using good hash functions for the bloom filters, they'll tell you that - with high probability - you don't have to search in neither the first, second nor third part. Thus you save yourself from checking 33 characters and instead only have to check 16 bytes (for the 4 bloom filters). This is still O(n), just with a constant (fractional) factor (and in order for this to be effective you'll need to choose bigger parts, to minimize the overhead of calculating the hash functions for the search character).

Using a recursive, tree-like approach should get you near O(log n):

The quick brown fox jumps over the lazy dog 
   |   |   |   |   |   |   |   |---|-X-|   |  (1 Byte)
       |       |       |       |---X---|----  (2 Byte)
               |               |-----X------  (3 Byte)
-------------------------------|-----X------  (4 Byte)
---------------------X---------------------|  (5 Byte)

In this configuration one needs (again, assuming we got lucky and didn't get a false positive from one of the filters) to check

5 + 2*4 + 3 + 2*2 + 2*1 bytes

to get to the final part (where one needs to check 3 characters until finding the a).

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)

share|improve this answer
    
Dear downvoter, please explain why you think that my answer isn't helpful. – Daniel Jour Mar 20 at 8:47

If the string is going to be searched multiple times (typical "search" problem), solution can be O(1). Solution is to build an index.

E.g :

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.