Longest Common Substring

Problem definition from http://en.wikipedia.org/wiki/Longest_common_substring_problem

the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.

 Note: this is different from longest common subsequence (http://dream-e-r.blogspot.com/2014/07/longest-common-subsequence.html). Basically there will be ~2^n (exponential) subsequences, whereas there will be only ~n^2 substrings.

Brute Force

Brute force algorithm is pretty simple - basically getting all the substrings from the given two arrays O(n^2), and then iterating over them to find the common longest substring ((O(n^2*n^2)*n) == )(n^5)).

Solving the problem using Dynamic Programming

Say, LCSuffix(Xi, Yj) is the longest common suffix of Xi and Yj, then

 

LCSuffix(Xi, Yj) = 0 if Xi != Xj

                            = 1 + LCSuffix(Xi-1, Yj-1)

 

Then, LCSubstring = Max(for all LCSuffix(Xi, Yj))

Here is the corresponding code in C# and their unit tests:

Also answered the question @ http://stackoverflow.com/questions/10248728/how-to-find-longest-common-substring-using-c/25057217#25057217 

Code Snippet

10. [TestClass]
11.     public class LongestCommonSubstring
12.     {
13.         class LCSubstring
14.         {
15.             public int Length = 0;
16.             public List<Tuple<int, int>> indices = new List<Tuple<int, int>>();
17.         }
18.         public string[] LongestCommonSubStrings(string A, string B)
19.         {
20.             int[][] DP_LCSuffix_Cache = new int[A.Length+1][];
21.             for (int i = 0; i <= A.Length; i++)
22.             {
23.                 DP_LCSuffix_Cache[i] = new int[B.Length + 1];
24.             }
25.             LCSubstring lcsSubstring = new LCSubstring();
26.             for (int i = 1; i <= A.Length; i++)
27.             {
28.                 for (int j = 1; j <= B.Length; j++)
29.                 {
30.                     //LCSuffix(Xi, Yj) = 0 if X[i] != X[j]
31.                     //                 = LCSuffix(Xi-1, Yj-1) + 1 if Xi = Yj
32.                     if (A[i - 1] == B[j - 1])
33.                     {
34.                         int lcSuffix = 1 + DP_LCSuffix_Cache[i - 1][j - 1];
35.                         DP_LCSuffix_Cache[i][j] = lcSuffix;
36.                         if (lcSuffix > lcsSubstring.Length)
37.                         {
38.                             lcsSubstring.Length = lcSuffix;
39.                             lcsSubstring.indices.Clear();
40.                             var t = new Tuple<int, int>(i, j);
41.                             lcsSubstring.indices.Add(t);
42.                         }
43.                         else if(lcSuffix == lcsSubstring.Length)
44.                         {
45.                             //may be more than one longest common substring
46.                             lcsSubstring.indices.Add(new Tuple<int, int>(i, j));
47.                         }
48.                     }
49.                     else
50.                     {
51.                         DP_LCSuffix_Cache[i][j] = 0;
52.                     }
53.                 }
54.             }
55.             if(lcsSubstring.Length > 0)
56.             {
57.                 List<string> substrings = new List<string>();
58.                 foreach(Tuple<int, int> indices in lcsSubstring.indices)
59.                 {
60.                     string s = string.Empty;
61.                     int i = indices.Item1 - lcsSubstring.Length;
62.                     int j = indices.Item2 - lcsSubstring.Length;
63.                     Assert.IsTrue(DP_LCSuffix_Cache[i][j] == 0);
64.                     for(int l =0; l<lcsSubstring.Length;l++)
65.                     {
66.                         s += A[i];
67.                         Assert.IsTrue(A[i] == B[j]);
68.                         i++;
69.                         j++;
70.                     }
71.                     Assert.IsTrue(i == indices.Item1);
72.                     Assert.IsTrue(j == indices.Item2);
73.                     Assert.IsTrue(DP_LCSuffix_Cache[i][j] == lcsSubstring.Length);
74.                     substrings.Add(s);
75.                 }
76.                 return substrings.ToArray();
77.             }
78.             return new string[0];
79.         }
80.         [TestCategory(Constants.DynamicProgramming)]
81.         [TestMethod]
82.         public void LCSubstringTests()
83.         {
84.             string A = "ABABC", B = "BABCA";
85.             string[] substrings = this.LongestCommonSubStrings(A, B);
86.             Assert.IsTrue(substrings.Length == 1);
87.             Assert.IsTrue(substrings[0] == "BABC");
88.             A = "ABCXYZ"; B = "XYZABC";
89.             substrings = this.LongestCommonSubStrings(A, B);
90.             Assert.IsTrue(substrings.Length == 2);
91.             Assert.IsTrue(substrings.Any(s => s == "ABC"));
92.             Assert.IsTrue(substrings.Any(s => s == "XYZ"));
93.             A = "ABC"; B = "UVWXYZ";
94.             string substring = "";
95.             for(int i =1;i<=10;i++)
96.             {
97.                 A += i;
98.                 B += i;
99.                 substring += i;
100.                 substrings = this.LongestCommonSubStrings(A, B);
101.                 Assert.IsTrue(substrings.Length == 1);
102.                 Assert.IsTrue(substrings[0] == substring);
103.             }
104.         }
105.     }