/* Pravin Baskaran [PB]*/

using System;

using System.Collections.Generic;

​

public class JoyWorld

{

    /*Given two strings S1 & S2, Find the length of longest common sequence in both strings. 

      And print all the existing longest common sequences in both strings. */

    /* For example

        Input:  S1 = SOLARSYSTEM, S2 = EYSTSEOELEAR

        Output: SOLAR

        Input:  S1 = OPTIMUSPRIME, S2 = JOYPABRIME

        Output: OPRIME

        Input:  S1 = ACEPIBOSSJKL, S2 = MSOPOBSUV

        Output: PBS , POS

    */

    static int [,] Board;

    public static void Main()

    {

        string S1 = "SOLARSYSTEM";

        string S2 = "EYSTSEOELEAR";

        FindLCS(S1, S2);

        S1 = "OPTIMUSPRIME";

        S2 = "JOYPABRIME";

        FindLCS(S1, S2);

        S1 = "ACEPIBOSSJKL";

        S2 = "MSOPOBSUV";

        FindLCS(S1, S2);

        S1 = "OPQPROP";

        S2 = "PRSQOPO";

        FindLCS(S1, S2);

        S1 = "MILKYWAYGALAXY";

        S2 = "STAOPGEAELAEXSY";

        FindLCS(S1, S2);

    }

    private static void FindLCS(string S1, string S2)

    {

        Console.Write("In {0} and {1} , LCS length is {2}",  S1, S2, GetLCSLength(S1, S2));

        Console.WriteLine("");

        HashSet<String> lcsSet = BackTrackAllLCS(S1, S2, S1.Length, S2.Length);

        Console.Write("LCS Sequence  ");

        Console.WriteLine(string.Join(", ", lcsSet));   

        Console.WriteLine();

    }

    private static int GetLCSLength(string S1, string S2)

    {

        Board = new int[S1.Length + 1, S2.Length + 1];

        // Build LCS Board[S1.Length + 1, S2.Length + 1]

        for (int row = 0; row <= S1.Length; row++)

        {

            for (int column = 0; column <= S2.Length; column++)

            {

                if (row == 0 || column == 0)

                {

                    Board[row, column] = 0;

                }

                else if (S1[row - 1] == S2[column - 1])

                {

                    Board[row, column] = Board[row - 1, column - 1] + 1;

                }

                else

                {   

                    Board[row, column] = Math.Max(Board[row - 1, column], Board[row, column - 1]);

                }

            }

        }

        return Board[S1.Length, S2.Length];

    }

    private static HashSet<String> BackTrackAllLCS(string S1, string S2, int firstLen, int secondLen)

    {

        //Store all possible LCS

        HashSet<String> lcsSet = new HashSet<String>();

​

        if (firstLen == 0 || secondLen == 0)

        {

            lcsSet.Add("");

            return lcsSet;

        }

​

        // If the last characters of S1 and S2 are same

        if (S1[firstLen - 1] == S2[secondLen - 1])

        {

            HashSet<String> portions = BackTrackAllLCS(S1, S2, firstLen - 1, secondLen - 1);

            foreach (String portion in portions)

                lcsSet.Add(portion + S1[firstLen - 1]);

        }

        else

        {

            if (Board[firstLen - 1, secondLen] >= Board[firstLen, secondLen - 1])

                lcsSet = BackTrackAllLCS(S1, S2, firstLen - 1, secondLen);

​

            if (Board[firstLen, secondLen - 1] >= Board[firstLen - 1, secondLen])

            {

                HashSet<String> portions = BackTrackAllLCS(S1, S2, firstLen, secondLen - 1);

                foreach (string portion in portions)

                    lcsSet.Add(portion);

            }

        }

        return lcsSet;

    }                     

}