2

Can any one explain what algorithm used in strcmp to compare two string in C programming ?

I didnt understand the return value from this, It uses any algorithm like 'Levenstien algorithm' to find out distance between two string...

Sahal
  • 4,046
  • 15
  • 42
  • 68

3 Answers3

7

The GNU implementation of the standard C library, glibc, is open source and you can just read strcmp.c if you are curious. There is not much to it. Here it is:

/* Compare S1 and S2, returning less than, equal to or
   greater than zero if S1 is lexicographically less than,
   equal to or greater than S2.  */
int strcmp (const char *p1, const char *p2)
{
  register const unsigned char *s1 = (const unsigned char *) p1;
  register const unsigned char *s2 = (const unsigned char *) p2;
  unsigned reg_char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
        return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}
David Grayson
  • 84,103
  • 24
  • 152
  • 189
4

strcmp is not a string distance algorithm. It is a string comparison algorithm and the only thing it is required to tell you is whether the two strings are equal (return code zero) or if not, which of the two strings is "greater" for some meaning of that word (a positive or negative value).

The magnitude of the return result is not specified, i.e. it can always return either 1, 0, or -1; or it can return an actual integral distance for some measure of distance (e.g. Levenstein, simple subtraction, etc.). In practice, strcmp is never implemented with an actual string distance algorithm for performance reasons (do the least amount of work to determine the equivalence of two strings and get out).

Mahmoud Al-Qudsi
  • 28,357
  • 12
  • 85
  • 125
  • Distance algorithm is nothing but comparison algorithm only. It will say how far two string is equal. What is my questions is what algorithm strcmp is used in the backend. strcmp is the function written by some one, i need to know the logic of it. – Sahal Jun 07 '12 at 07:14
  • @Sahal and that's what I said in my post. You'll get the fastest distance algorithm, not levenstein, et. al. – Mahmoud Al-Qudsi Jun 07 '12 at 15:42
3

these documentations for strcmp() are pretty clear

A zero value indicates that both strings are equal. A value greater than zero indicates that the first character that does not match has a greater value in str1 than in str2; And a value less than zero indicates the opposite.

in other word, it checks for lexicographical order, or even more accurate alphabetical order between the two strings.

amit
  • 175,853
  • 27
  • 231
  • 333
  • 2
    Lexicographical order in terms of bytes/code units, not (wide) characters, much less any cultural conventions for lexicographical ordering. `strcoll` is there for the latter. – R.. GitHub STOP HELPING ICE Jun 07 '12 at 07:04