Most memory efficient way for searching within a string in C

Question

What is the most memory efficient way to search within a string in ANSI C? (put the code up)

An example where this is needed is in embedded devices that are very short on available memory but nowadays have reasonable clock cycles.

Answer 1

It depends on what you're looking for...but strchr() or strstr() are often appropriate. And those are extremely memory efficient since they use no extra memory.

Answer 2

If you are looking for a substring, then strstr is very memory efficient. and for a char, strchr is also very memory efficient. Neither need extra storage.

I'm not sure if there is anything more that you are looking for.

Answer 3

I suppose it depends on what you're searching for, but a linear search/comparison uses no more memory than the two strings (the 'host', and the 'token'). For example:

char host[] = "this is my string to search";
char token[] = "y st";
int k = 0;
while(host[k] != '\0'){
  for(int t=0; (token[t]!='\0' && host[k+t]!='\0');){
    if(host[k] == token[t]){
      t++;  // we matched the first char of token, so advance
    }
    else{   // no match yet, reset the token counter and move along the host string
      k++;
      t = 0;
    }
  }
  k++;
}

(I may be slightly off in the implementation, but hopefully you get my idea.)

Library functions like strstr should be worth looking at, too.

Answer 4

Advancing one character at a time is Θ((n-m+1) m). Check into the Boyer-Moore and Knuth-Morris-Pratt algorithms for more efficient ways of searching for substrings -- both as low as O(n). Your handy algorithms textbook should discuss both of them. The standard C library strstr function implements one or both, so use that instead of rolling your own.

Answer 5

Depending on the kind of search and the boundary conditions there is a large number of different algorithms for searching a sub-string in a string. A large collection is available here: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Answer 6

I recently came across this problem and just want to share my thoughts.

"Memory efficient" as I interpreted it is the ability to search a long string of size M given only N amount of available memory, M > N. This is alternative to an efficient use of memory per character available in the string to search. And I feel may be more relevant to the original poster's embedded environment (that may have a large storage).

Regardless of which algorithm you use to do the comparison (the more efficient the better of course), I would choose to use a circular buffer (which should be greater than the string you're search for, at least 2X perhaps?) and continuously load the stream of characters to the buffer while the search algorithm advances. The search algorithm must be able to know how to wrap around the circular buffer (or add a level of indirection to hide the circular buffer from the search algorithm).