Longest Common Subsequence

LCS.cs

using System;
using System.Text;
using System.Collections.Generic;

public static class LCS
{
	struct LCSInfo
	{
		public int Len;
		public int BackType;
		
		public LCSInfo(int l, int bt)
		{
			Len = l;
			BackType = bt;
		}
	}
	
	static Dictionary<ulong, LCSInfo> s_lcsBuffer = new Dictionary<ulong, LCSInfo>();
	static StringBuilder s_lcsBuilder = new StringBuilder(4096);
	
	static ulong GenBufferKey(int v1, int v2)
	{
		ulong v1l = (ulong)v1;
		ulong v2l = (ulong)v2;
		return (v1l << 32) | v2l;
	}
	
	static void GetLCS(string str1, string str2, int length1, int length2)
	{
		if (length1 >= 1 && length2 >= 1)
		{
			var key = GenBufferKey(length1, length2);
			if (s_lcsBuffer.ContainsKey(key))
			{
				var info = s_lcsBuffer[key];
				if (info.BackType == 1)
				{
					s_lcsBuilder.Insert(0, str1[length1 - 1]);
					GetLCS(str1, str2, length1 - 1, length2 - 1);
				}
				else if (info.BackType == 2)
				{
					GetLCS(str1, str2, length1 - 1, length2);
				}
				else if (info.BackType == 3)
				{
					GetLCS(str1, str2, length1, length2 - 1);
				}
			}
		}
	}
	
	public static string CalcLCS(string s1, string s2)
	{
		if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
		{
			return null;
		}
		
		s_lcsBuffer.Clear();
		s_lcsBuilder.Length = 0;
		
		for (int i = 0; i <= s1.Length; ++i)
		{
			s_lcsBuffer[GenBufferKey(i, 0)] = new LCSInfo();
		}
		
		for (int j = 0; j <= s2.Length; ++j)
		{
			s_lcsBuffer[GenBufferKey(0, j)] = new LCSInfo();
		}
		
		for (int i = 1; i <= s1.Length; ++i)
		{
			for (int j = 1; j <= s2.Length; ++j)
			{	
				if (s1[i - 1] == s2[j - 1])
				{
					var last = s_lcsBuffer[GenBufferKey(i - 1, j - 1)];
					s_lcsBuffer[GenBufferKey(i, j)] = new LCSInfo(last.Len + 1, 1);
				}
				else
				{
					var pending1 = s_lcsBuffer[GenBufferKey(i - 1, j)];
					var pending2 = s_lcsBuffer[GenBufferKey(i, j - 1)];
					if (pending1.Len > pending2.Len)
					{
					    s_lcsBuffer[GenBufferKey(i, j)] = new LCSInfo(pending1.Len, 2);
					}
					else
					{
						s_lcsBuffer[GenBufferKey(i, j)] = new LCSInfo(pending2.Len, 3);
					}
				}
			}
		}
		
		GetLCS(s1, s2, s1.Length, s2.Length);
		return s_lcsBuilder.ToString();
	}
}