Longest Common Sub sequence

What is Longest Common Sub sequence?


Longest Common Sub sequence is longest consecutive/non consecutive matching characters of the two strings..

Lets take two strings

Str1 = "XMJYAUZ"
Str2 = "MZJAWXU"

Longest common subsequence is "MJAU"..

This problem can be very easily solved using dynamic programming.

Here is the C# Code below

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Math;

namespace maxCommonSubstring

{

    class Program

    {

        static void Main(string[] args)

        {

            string str1 = "hello12india2125";

            string str2 = "hel2125ino";

             Console.WriteLine(LongestCommonSubsequence(str1, str2));

        }

        public static int LongestCommonSubsequence(string str1, string str2)

        {

            int maxSubSeq = 0;

           // Create 2-d Array

            int[,] arr = new int[str1.Length + 1, str2.Length + 1];

          // Initialize 2 - d array 

        // Note only zeroth column and zeroth row is assigned value 0

      // Can be skipped as well as by default they are Zero in C#

            for (int i = 0; i < str2.Length; i++)

            {

                arr[0, i] = 0;

            }

            for (int i = 0; i < str1.Length; i++)

            {

                arr[i, 0] = 0;

            }

         // Start Filling the table 

        // if Character match add 1 to diagonal element of 2 - d array and fill it

       // Else put the max of the elements on its top or  on its left ..

      // Keep track of the size using a variable "maxSubSeq"

            for (int i = 1; i <= str1.Length; i++)

            {

                for (int j = 1; j <= str2.Length; j++)

                {

                     if (str1[i - 1] == str2[j - 1])

                    {

                        //Character match add 1 to diagonal element of 2 - d array

                        arr[i, j] = arr[i - 1, j - 1] + 1;

                        if (arr[i, j] > maxSubSeq)

                        {

                            maxSubSeq = arr[i, j];

                        }

                    }

                    else

                    {

                          // Else put the max of the elements on its top or  on its left ..

                          arr[i, j] = Math.Max(arr[i, j - 1] ,  arr[i - 1, j]);

                    }

                }

            }

            return maxSubSeq;

     }

}

Complexity :

Space complexity O(n*m) since we are using the 2-d array where n and m are length of the given 2 strings

Computational complexity O(n*m) since we filling the 2-d array in loops  where n and m are length of the given 2 strings

Hope you  liked it....