A Simple String Matching Algorithm

Written by Raza on. Posted in C++

Human Beings like to play with string in their daily life. We deal with all sorts of alphabets and words and often try to compare them with one another. To check whether we have two given set of characters equal or not, we make use of string matching algorithms. To match the two given strings, we use then to look for equality in both the strings for the desired results. A simple string matching algorithm is to iterate over each alphabet and match correspondingly. Let us see in detail how we do that. 

The string matching algorithm we are developing would tell us whether the first given string is equal to, less than or greater than the second string. Alphabets are compared similar to digits. For instance, `b` is greater than `a` and `y` is smaller than `z`. If all alphabets are same, strings would be equal. As soon as a different character is encountered, the string with higher alphabet would be greater. So strings `abc` and `abc` are equal, strings `abc` is greater than `abb` and `b` is greater than `ab`.

Our string matching algorithm would compare the two strings up to the size of the larger string. So there remains no need in any case to check if one string is larger or not. This way, even if one string is larger in size, it might be possible that it is a smaller one. For example, `yz` is greater than `abc`. Then there is a case when there are two strings of unequal sizes and the smaller one is present in the larger one too. For example, `abc` and `abcd` would not be equal and the latter would be larger. For all these things to happen correctly, we have to make sure or assume that the strings passed have been null terminated.

There is another case we have to consider as well. The two strings given to us are empty or null strings. In this case, no comparison would be made although the strings are equal. Another similar scenario would be when one string is a null string and the other is not. So there should be a method to check these conditions as well.


Here is a simple source code of our simple string matching algorithm which caters for all our basic needs for now.


int string_compare (const char str1[], const char str2[])
.  int status = 0 ;
.  for (int i = 0 ; (str1[i] != '\0' || str2[i] != '\0') ; ++i)
.  {
.   if (str1[i] < str2[i])
.   {
.    status = -1 ;
.    break ;
.   }
.   else if (str1[i] > str2[i])
.   {
.    status = 1 ;
.    break ;
.   }
.  }
.  return status ;

int main ()
.  char str1[] = "hello there" ;
.  char str2[] = "hello hi" ;
.  cout << string_compare(str1, str2) ;

  The algorithm which we have developed has been implemented in C++ Library by the name of a function known as strcmp(). Its prototype is exactly the same as the string matching algorithm we have just developed. Its just that it is more flexible and better to use. To use this function, you might want to include the cstring.h libary in some compilers.

Tags: , , ,

Trackback from your site.

Leave a comment