Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@k0ksi
Created October 13, 2015 11:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save k0ksi/b6a7e06cd29b443d6076 to your computer and use it in GitHub Desktop.
Save k0ksi/b6a7e06cd29b443d6076 to your computer and use it in GitHub Desktop.
using System.Collections.Generic;
namespace Longest_Common_Subsequence
{
using System;
public class LongestCommonSubsequence
{
public static void Main()
{
Console.Write("firstStr = ");
var firstStr = Console.ReadLine();
Console.Write("secondStr = ");
var secondStr = Console.ReadLine();
var lcs = FindLongestCommonSubsequence(firstStr, secondStr);
Console.WriteLine("Longest common subsequence:");
Console.WriteLine(" first = {0}", firstStr);
Console.WriteLine(" second = {0}", secondStr);
Console.WriteLine(" lcs = {0}", lcs);
}
public static string FindLongestCommonSubsequence(string firstStr, string secondStr)
{
int firstLen = firstStr.Length + 1;
int secondLen = secondStr.Length + 1;
var lcs = new int[firstLen, secondLen];
for (int i = 1; i < firstLen; i++)
{
for (int j = 1; j < secondLen; j++)
{
if (firstStr[i - 1] == secondStr[j - 1])
{
lcs[i, j] = lcs[i - 1, j - 1] + 1;
}
else
{
lcs[i, j] = Math.Max(lcs[i - 1, j], lcs[i, j - 1]);
}
}
}
return RetrieveLcs(firstStr, secondStr, lcs);
}
public static string RetrieveLcs(string firstStr, string secondStr, int[,] lcs)
{
List<char> lcsLetters = new List<char>();
int x = firstStr.Length;
int y = secondStr.Length;
while (x > 0 && y > 0)
{
if ((firstStr[x - 1] == secondStr[y - 1]))
{
lcsLetters.Add(firstStr[x]);
x--;
y--;
}
else if (lcs[x, y] == lcs[x - 1, y])
{
x--;
}
else
{
y--;
}
Console.WriteLine(string.Join(", ", lcsLetters));
}
lcsLetters.Reverse();
return new string(lcsLetters.ToArray());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment