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 length of longest common substring from s1, s2,
         * s1's substring ends at postion i,
         * and s2's substring ends at position j
         *
         * Design issues:
         *
         * 4 variables - memo, longest, end1, searchFirstRowCol
         * 1. memorization using two dimension array - memo
         * 2. variable int longest - get maximum length
         * 3. variable int end1    - string s1 - end position - s1's substring end position
         * 4. vraiable bool searchFirstRowCol - check first row and first col to update maximum length
         */
        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.
        }
    }
}