Daily question series: common substring calculation

link ：https://www.nowcoder.com/questionTerminal/98dc82c094e043ccb7e0570e5342dd1b
source ： Cattle from

Given two strings that contain only lowercase letters , Calculate the length of the largest common substring of two strings .

notes ： The definition of substring means that a string deletes some of its prefixes and suffixes （ It's also possible to delete ） String formed after .
Data range ： String length ：1≤s≤150
Advanced ： Time complexity ：O(n^3) , Spatial complexity ：O(n)

Their thinking ：
For dynamic programming , We can't solve this big problem all at once , It needs to be divided into small problems , Let's first look at the length of the maximum common substring between the substrings of each string , Then use the solution of the small problem to push down the big problem

Let's define a function ：
F（i,j） Represents the first string i The end of the first character and the second string j The length of the largest common substring ending in characters

for instance ：

F（1,1） Express ： The of the first string starts with 1 Characters a The ending substring , The of the second string starts with 1 Characters w The ending substring , The maximum common substring length is 0

In the same way ：
F（2,3）: … s,… r, The maximum common substring length is 0
F（4,7）: …f,… f, The maximum common substring length must be greater than or equal to 1 了 （f It's the same ,f The previous one may be the same ）

Spread it ：
If the first i Characters != The first j Characters
F（i,j）=0

The first i Characters == The first j Characters
F(i,j)=F(i-1,j-1)+1

such as F(1,4)=1 character string a
F(2,5)=F(1,4)+1=2 character string as
F(3,6)=F(2,5)+1=3 character string asd

The initial state ：F（i,0）=F(0,j)=0
（ You compare a string to an empty string , Their substring must be 0）
Return value ：max(F(i,j))

The code is as follows ：

import java.util.*;
public class Main{
    
    public static int getMaxLen(String str1,String str2){
    
        char[] arr1=str1.toCharArray();
        char[] arr2=str2.toCharArray();
        int l1=arr1.length;
        int l2=arr2.length;
        int[][] maxSubLen=new int[l1+1][l2+1];
        int maxLen=0;
        for(int i=1;i<=l1;i++){
    
            for(int j=1;j<=l2;j++){
    
                if(arr1[i-1]==arr2[j-1]){
    
                    //F(i,j)=F(i-1,j-1)+1
                    maxSubLen[i][j]=maxSubLen[i-1][j-1]+1;

                    // Whether the maximum value needs to be updated 
                    if(maxLen<maxSubLen[i][j]){
    
                        maxLen=maxSubLen[i][j];
                    }
                }// If the range , You don't have to worry about it , The default in the original array is 0
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
    
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.nextLine();
        String str2=scanner.nextLine();
        int x=getMaxLen(str1,str2);
        System.out.println(x);
    }
}