The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. This C++ program finds the longest common sub-sequence between 2 strings. It implements the most famous dynamic programming algorithm. Strings must be null-terminated strings. There are always two cases when matching two strings. First case is when any character of two strings match, the length of LCS improves. Second case, when character of two strings don’t match.

two cases of LCS

//******
// lcs.c
//** - this package is provided as is with no warranty.
//** - the author is not responsible for any damage caused
//**   either directly or indirectly by using this package.
//** - anybody is free to do whatever he/she wants with this
//**   package as long as this header section is preserved.
//** Created on 2005-01-22 by
//** - Roger Zhang (rogerz@cs.dal.ca)
//** Modifications
//** -
//** Last compiled under Linux with gcc-3
//**************************

#include
#include

char *lcs(char *s, char *t)
{
   char *result;
   int n = strlen(s), m = strlen(t), i, j, **a;

   if (!n || !m) { /* empty input string */
      return "";
   }

   a = (int**)calloc(n + 1, sizeof(int*));
   a[0] = (int*)calloc((n + 1) * (m + 1), sizeof(int));

   for (i = a[0][0] = 0; i <= n; i++) { /* find the length */
      if (!i || (a[i] = a[i - 1] + m)) {
         for (j = 0; j <= m; j++) {
            if (!i || !j) { /* initialize the base row/column */
               a[i][j] = 0;
            } else if (s[i - 1] == t[j - 1]) { /* diagonal step */
               a[i][j] = a[i - 1][j - 1] + 1;
            } else { /* horizontal or vertical step */
               a[i][j] = a[i][j - 1] > a[i - 1][j] ? a[i][j - 1] : a[i - 1][j];
            }
         }
      } else {
         abort(); /* memory failure */
      }
   }

   if (!(i = a[n][m])) {
      return ""; /* no common sub-sequence */
   }

   if (!(result = (char*)malloc(i + 1)) || (result[i] = '\0')) {
      abort(); /* memory allocation failed */
   }

   while (n > 0 && m > 0) { /* back track to find the sequence */
      if (s[n - 1] == t[m - 1] && m--) {
         result[--i] = s[--n];
      } else {
         a[n][m - 1] >= a[n - 1][m] ? m-- : n--;
      }
   }

   free(a[0]);
   free(a);

   return result;
}
Tagged with: C/C++ languageProgrammingSource Code
 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.