Longest common substring between two strings using DP- Algo 6

Self understanding - Substring between two strings

Java implementation:

package com.javadsalgo.Sorting;

public class LongestCommonSubstring {

     public static void main(String[] args) {

          String str2 = "APARDEA";

          String str1 = "ZPARCDA";

          System.out.println("Longest common substring is :"

                   + find(str1.toCharArray(), str2.toCharArray()));

     }

     public static int find(char[] str1, char[] str2) {

          int temp[][] = new int[str1.length + 1][str2.length + 1];

          String[][] solution = new String[str1.length + 1][str2.length + 1];

          String answer="";

          int max = 0,iInd=0,jInd=0;

          for (int i = 1; i <= str1.length; i++) {

              for (int j = 1; j <= str2.length; j++) {

                   if (str1[i - 1] == str2[j - 1]) {

                        temp[i][j] = temp[i - 1][j - 1] + 1;

                        solution[i][j]="diagonal";

                        if (max < temp[i][j])

                             {

                             max = temp[i][j];

                             iInd=i;

                             jInd=j;

                             }

                   }

              }

          }

          String sol=solution[iInd][jInd];

          while(sol=="diagonal"){

              if(solution[iInd][jInd].equals("diagonal"))

              {

                   answer+=str1[iInd-1];

                   iInd--;jInd--;

              }

              sol=solution[iInd][jInd];

          }

          StringBuffer rev= new StringBuffer(answer);

          System.out.println(rev.reverse());

          return max;

     }

}

Output:

PAR

Longest common substring is :3