top of page
Caută
  • Poza scriitoruluioanaunciuleanu

Longest common subsequence algorithm in C++


Having two strings, you have to find the longest common subsequence. This means that you have to find how many letters are found in both strings, in the same order, and not necessarily adjacent. For example, the string CALENDAR and CABLNDR have as the longest common subsequence CALNDR. The letters are spread along the two strings but are found in the same order.


// Longest common subsequence algorithm
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

int longestCommonSubsequence( char *firstString, char *secondString, int lengthOfFirstString, int lengthOfSecondString)
{
   int lengthStrings[lengthOfFirstString + 1][lengthOfSecondString + 1];

   for (int i = 0; i <= lengthOfFirstString; i++)
   {
     for (int j = 0; j <= lengthOfSecondString; j++)
     {
       if (i == 0 || j == 0)
       {
           lengthStrings[i][j] = 0;
       }
       else if (firstString[i-1] == secondString[j-1])
       {
           lengthStrings[i][j] = lengthStrings[i-1][j-1] + 1;
       }
       else
       {
           lengthStrings[i][j] = max(lengthStrings[i-1][j], lengthStrings[i][j-1]);
       }
     }
   }

   int lengthLCS = lengthStrings[lengthOfFirstString][lengthOfSecondString];
   int index = lengthStrings[lengthOfFirstString][lengthOfSecondString];

   char longestCommonSubseq[index + 1];
   longestCommonSubseq[index] = '\0';

   int i = lengthOfFirstString;
   int j = lengthOfSecondString;

   while (i > 0 && j > 0)
   {
      if (firstString[i - 1] == secondString[j - 1])
      {
          longestCommonSubseq[index - 1] = firstString[i - 1];
          i--;
          j--;
          index--;
      }
      else if (lengthStrings[i - 1][j] > lengthStrings[i][j - 1])
      {
          i--;
      }
      else
      {
           j--;
      }
   }
   cout << "Longest Common Subsequence of " << firstString << " and " << secondString << " is " << longestCommonSubseq << " with length: " << lengthLCS << endl;
}

int main()
{
  char firstString[] = "CALENDAR";
  char secondString[] = "CABLNDR";
  int lengthOfFirstString = strlen(firstString);
  int lengthOfSecondString = strlen(secondString);
  longestCommonSubsequence(firstString, secondString, lengthOfFirstString, lengthOfSecondString);
  return 0;
}


Longest   Common Subsequence of CALENDAR and CABLNDR is CALNDR with length: 6

155 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no overlapping, in order to obtain the maximum profit. Solution: 1. static

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed vertically 2 x 1 or horizontally as 1 x 2. Solution: 1. static

bottom of page