longest common substring - Dynamic programming solution - first writing followed by static analysis, test case result, bug fixes etc.

longestCommonSubstringDp1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace longestCommonSubstringDP
{
    class Program
    {
        static void Main(string[] args)
        {
            string test = longestCommonSubstring("abc123def", "hij123klmn");
            string testEdgecaseRow0 = longestCommonSubstring("1abc","def1ghi"); // edge case: line 50-58
            string testEdgecaseCol0 = longestCommonSubstring("abc1def","1ghijkl"); 
        }

        /*
         * Lintcode #79 - longest common substring 
         * 
         * Practice using Dynamic programming solution
         * 
         * Time complexity: O(nm), space complexity: O(nm), n is string s1's length, 
         * m is string s2's length
         * 
         * Using Dynamic programming, bottom up 
         * Based on the recurrence formula
         * T(i+1, j+1) = T(i,j) + 1, if s[i+1] = s[j+1], 
         *             = 0, if s[i+1] != s[j+1]
         * T(i,j) stands for longest common substring from s1, s2, 
         * s1's substring ends at postion i, 
         * and s2's substring ends at position j
         *             
         * Design issues: 
         * 1. memorization using two dimension array
         * 2. 
         */
        public static string longestCommonSubstring(string s1, string s2)
        {
            if (s1 == null || s1.Length == 0 || s2 == null || s2.Length == 0)
                return string.Empty;

            int len1 = s1.Length;
            int len2 = s2.Length; 

            int[,] memo = new int[len1, len2];

            // first column of 2-dimension matrix 
            int  end1 = 0;   // end position of string 1 
            int  longest = 0;
            bool searchFirstRowCol = true;            

            for (int i = 0; i < len1; i++)
            {
                memo[i, 0] = (s1[i] == s2[0]) ? 1 : 0;
                if (searchFirstRowCol && memo[i, 0] > 0) // static analysis - added
                {
                    end1 = i; // found by test case! 
                    longest = 1;
                    searchFirstRowCol = false;
                }
            }

            for (int j = 0; j < len2; j++)
            {
                memo[0, j] = (s1[0] == s2[j]) ? 1 : 0;
                if (searchFirstRowCol && memo[0, j] > 0)
                {
                    end1 = 0; 
                    longest = 1;
                    searchFirstRowCol = false; 
                }
            }                                    

            for(int i=1; i< len1; i++)
                for (int j = 1; j < len2; j++)
                {
                    memo[i, j] = (s1[i] == s2[j]) ? (memo[i - 1, j - 1] + 1) : 0;
                    if (memo[i, j] > longest)
                    {
                        longest = memo[i, j];
                        end1 = i; 
                    }
                }

            return longest == 0 ? string.Empty : s1.Substring(end1 - longest + 1, longest); // start position check, length check. 
        }
    }
}