fullstackDevelopment/Java/LongestCommonSubstring.java at 2aaf4140edfaad80d55f5a151af06ad04818ad9b · ishangoyal13/fullstackDevelopment · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Calculate the lenght of longest Common substring
//Solution:
public class LongestCommonSubstring{

    public static void main(String []args){
       String a = "abcdxyz";
       String b = "xyzabcd";
       int i,j;
       int lena = a.length();
       int lenb = b.length();
       int[][] arr = new int[lena+ 1][lenb+1];

       for(i = 0; i<= lena; i++ )
       {
           for(j = 0;j<=lenb; j++)
           {
               if(i==0 || j==0)
               arr[i][j] = 0;
           }
       }
       for(i = 1; i<= lena; i++ )
       {
           for(j = 1;j<=lenb; j++)
           {
               if(a.charAt(i-1) == b.charAt(j-1))
               {
                   arr[i][j] = 1 + arr[i-1][j-1];
               }
               else
               arr[i][j] = 0;
           }
       }
       int max =0;
       for(i = 0; i<= lena; i++ )
       {
           for(j = 0;j<=lenb; j++)
           {

                    if(arr[i][j]>max)
                    {
                        max = arr[i][j];
                    }
           }
       }


       System.out.println("Longest Common Substring : "+max+" length");
   }
}