Return to Answer

As your code doesn't really work and I got quite interested by this problem : I took mjolka's precious comments into account.

As your code doesn't really work and I got quite interested by this problem : I took mjolka's precious comments into account.

Edit 2

I originally posted this as a different answer because it is not related to the beginning of this message in any way but this doesn't seem to be much appreciated. As it can be relevant to you, I'm posting this here.

As your code doesn't really work and I got quite interested by this problem : I took mjolka 's precious comments into account.

Re-adapting code from the link in his comment, here what I got :

public class MirrorString {
 /* Returns length of longest common substring of X and Y */
 public static int LCSubStr(int[] X /* WAS , int[] Y*/)
 {
 int m = X.length;
 int n = m; // WAS int n = Y.length;
 // Create a table to store lengths of longest common suffixes of
 // substrings. Notethat LCSuff[i][j] contains length of longest
 // common suffix of X and Y. The first row and
 // first column entries have no logical meaning, they are used only
 // for simplicity of program
 int[][] LCSuff = new int[m+1][n+1];
 int result = 0; // To store length of the longest common substring
 /* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */
 for (int i=0; i<=m; i++)
 {
 for (int j=0; j<=n; j++)
 {
 if (i == 0 || j == 0)
 LCSuff[i][j] = 0;
 else if (X[i-1] == X[n-j]) // WAS else if (X[i-1] == Y[j-1])
 {
 LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
 result = Math.max(result, LCSuff[i][j]);
 }
 else LCSuff[i][j] = 0;
 }
 }
 return result;
 }
 public static void main(String[] args) {
 System.out.println("Hello, world!");
 System.out.println(LCSubStr(new int[] {7, 7, 7, 5, 6, 7, 7})); // 3
 System.out.println(LCSubStr(new int[] {7, 7, 7, 7, 6, 7, 7})); // 5
 System.out.println(LCSubStr(new int[] {})); // 0
 System.out.println(LCSubStr(new int[] {1})); // 1
 System.out.println(LCSubStr(new int[] {1, 1})); // 2
 System.out.println(LCSubStr(new int[] {1, 1, 1})); // 3
 System.out.println(LCSubStr(new int[] {1, 2, 3, 2, 1})); // 5
 System.out.println(LCSubStr(new int[] {1, 2, 3, 8, 9, 3, 2, 1})); // 3
 System.out.println(LCSubStr(new int[] {1, 2, 1, 4})); // 3
 System.out.println(LCSubStr(new int[] {7, 1, 2, 9, 7, 2, 1})); // 2
 }
}

I have adapted the code a bit. Then, the only places where the algorithm has been changed are marked with WAS :

• only one argument is required now
• instead of accessing the j-1th element from J, we access the n-jth element from X (simulating a backward traversal).

Please note that things could be done in an even more efficient way using a different data structure as per the wikipedia page about Longest Common Substring problem .

Edit : bug found ?

On int[] num5 = {7, 7, 7, 7, 6, 7, 7};, the function returns 6 and I do not see why.