Finding length of longest common substring
1 /*Finding length of longest common substring using DP 2 * */ 3 import java.util.*; 4 public class Solution { 5 /* 6 * Returns length of longest common substring of 7 * X[0...m-1] and Y[0...n-1] 8 * */ 9 public static int LCSubStr(char X[], char Y[], int m, int n) { 10 /*Create a table to store lengths of longest common suffixes of substrings. 11 * Note that LCSuff[i][j] contains length of longest common suffix of X[0...i-1] and Y[0...j-1] 12 * The first row and first column entries have no logical meaning, they are only for the simplicity of program 13 * */ 14 15 int LCStuff[][] = new int[m+1][n+1]; 16 int result = 0;//to store the longest common substring 17 18 //Following steps build LCStuff[m+1][n+1] in bottom up fashion 19 for(int i = 0; i <= m; i++) { 20 for(int j = 0; j <= n; j++) { 21 if(i == 0 || j == 0) { 22 LCStuff[i][j] = 0; 23 }else if(X[i-1] == Y[j-1]){ 24 LCStuff[i][j] = LCStuff[i-1][j-1] + 1; 25 result = Integer.max(result, LCStuff[i][j]); 26 }else { 27 LCStuff[i][j] = 0; 28 } 29 } 30 31 } 32 33 return result; 34 } 35 36 //Driver Program to test above function 37 public static void main(String[] args) { 38 String X = "GeeksforGeeks"; 39 String Y = "GeeksQuiz"; 40 41 int m = X.length(); 42 int n = Y.length(); 43 44 System.out.println("Length of longest common substring is " + LCSubStr(X.toCharArray(), Y.toCharArray(), m,n)); 45 46 } 47 }
Print the longest common substring
1 /*Print longest common substring using DP 2 * */ 3 import java.util.*; 4 public class Solution { 5 /* 6 * Print longest common substring of 7 * X[0...m-1] and Y[0...n-1] 8 * */ 9 public static void printLCSubStr(String X, String Y, int m, int n) { 10 /*Create a table to store lengths of longest common suffixes of substrings. 11 * Note that LCSuff[i][j] contains length of longest common suffix of X[0...i-1] and Y[0...j-1] 12 * The first row and first column entries have no logical meaning, they are only for the simplicity of program 13 * */ 14 15 int LCStuff[][] = new int[m+1][n+1]; 16 int len = 0;//to store the length of longest common substring 17 /* To store the index of the cell which contains the maxium value. 18 * The cell's index helps in building up the longest common sustring from right to left. 19 **/ 20 21 int row = 0, col = 0; 22 23 //Following steps build LCStuff[m+1][n+1] in bottom up fashion 24 for(int i = 0; i <= m; i++) { 25 for(int j = 0; j <= n; j++) { 26 if(i == 0 || j == 0) { 27 LCStuff[i][j] = 0; 28 }else if(X.charAt(i-1) == Y.charAt(j-1)){ 29 LCStuff[i][j] = LCStuff[i-1][j-1] + 1; 30 if(len < LCStuff[i][j]) { 31 len = LCStuff[i][j]; 32 row = i; 33 col = j; 34 } 35 }else { 36 LCStuff[i][j] = 0; 37 } 38 } 39 } 40 // System.out.println("fin row = " + row); 41 // System.out.println("fin col = " + col); 42 // if true, then no common substring exists 43 if(len == 0) { 44 System.out.println("No Common Substring"); 45 return ; 46 } 47 48 // allocate space for the longest common substring 49 String resultStr = ""; 50 51 //traverse up diagonally from the (row, col) cell until LCStuff[row][col] ! = 0 52 //ex. len = 4, then (row, col) is 4 and then goes up diagonally, then you get 3-2-1-0 and append the chars from right to left in the result alongside the way 53 while(LCStuff[row][col] != 0) { 54 resultStr = X.charAt(row-1) + resultStr; //or Y[col-1] 55 --len; 56 57 //move diagonally up to previous cell 58 row--; 59 col--; 60 } 61 62 //print longest common substring 63 System.out.println("Longest common substring: " + resultStr); 64 } 65 66 //Driver Program to test above function 67 public static void main(String[] args) { 68 String X = "ABCXYZAY"; 69 String Y = "XYZABCB"; 70 71 int m = X.length(); 72 int n = Y.length(); 73 74 printLCSubStr(X, Y, m, n); 75 76 } 77 }