One 、 subject

Topic link ： Find two strings a,b The longest common substring in

Two 、 Topic analysis

Two ways of thinking , The first conventional idea , The second dynamic programming .

1. Conventional idea I

   By traversing two strings str1 And str2, Maintain the left and right pointers at the same time , Judge the longest repeated string .

1. Traverse each character of the shorter string as the starting point , Keep matching substrings
2. maintain Left pointer j, Right pointer k, The right pointer gradually approaches to the left
3. Satisfy the substring matching and the maximum substring length

import java.util.*;
public class Main{
    
    public static void main(String[] args) {
    
            Scanner sc = new Scanner(System.in);
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            // Judge which of the two strings is longer and which is shorter 
            if (str1.length() <= str2.length()) {
    
                longString(str1, str2);
            } else {
    
                longString(str2, str1);
            }
        }
    
    public static void longString(String str1,String str2){
    
        // Define the maximum length maxLen , Start subscript start
        int maxLen = 0;
        int start = 0;
        for(int i = 0;i<str1.length();i++){
    
            if(str1.length()-i-1 <= maxLen){
    
                break;
            } 
            for(int j =i,k=str1.length(); k>j ;k--){
    
                String subStr = str1.substring(i,k);
                if(str2.contains(subStr) && maxLen<subStr.length()){
    
                    maxLen = subStr.length();
                    start = j;
                    break;
                }
            }
        }
        System.out.println(str1.substring(start,start+maxLen));
        
    }
}

2. Conventional thinking 2

   utilize StringBuilder , Put the short string str1 Put it in StringBuilder in , Then traverse the long characters str2, Judge str2 Whether there is StringBuilder The characters of , If you have any , take StringBuilder The character of is updated to result, Until you find the longest public string . Practical and conventional thinking 1 similar .

import java.util.*;
public class Main{
    
    public static void main(String[] args) {
    
            Scanner sc = new Scanner(System.in);
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            // Judge which of the two strings is longer and which is shorter 
            if (str1.length() <= str2.length()) {
    
                longString(str1, str2);
            } else {
    
                longString(str2, str1);
            }
        }

ublic static void compare(String str1, String str2) {
    
            String result = "";
            for(int i =1;i<str1.length();i++){
    
                StringBuilder stringBuilder = new StringBuilder();
                for(int j =i-1;j<str1.length();j++){
    
                    if(str2.contains(stringBuilder.append(str1.charAt(j)))){
    
                        if(stringBuilder.length() > result.length()){
    
                            result = stringBuilder.toString();
                        }
                    }
                }
        }
        System.out.println(result);
    }
  }

---

3. Dynamic planning ideas

   A brief introduction to dynamic programming . Dynamic programming adopts the idea of divide and conquer to resolve the problem . Turn big problems into small ones , Then deduce the solution of the big problem from the small problem . It has four elements ：

1. state , The abstract state in the problem
2. State transition equation
3. State initialization
4. Return value

   We need to find out the state of this problem first . Our problem is ： The longest common substring of two characters .

   The sub problem is ：a Substring sum of b The longest common substring in the substring of
   Abstract subproblem ：a Before i Characters and b Before j Of the characters , Their longest common substring .

   If we want to know the specific content of the longest common substring , You need to know the length , The starting position , End position . So our state is as follows ：

F（i,j） : With a Of the i Substrings ending with characters and ending with b Of the j Character terminated substring , Their longest common substring length .

   Let's take an example ：

character string a：abcabcde
character string b：abcd

   Now let's illustrate by drawing ：

picture ）

   Through the above analysis , You can find , If a Of the i Characters and b Of the j Two characters are the same , be :

identical ：F(i,j) = F(i - 1, j- 1)+1, This is actually our transfer equation .
inequality ：0

   So what is our initial state and return value ？

The initial state F(0,0) = 0
Return value ： The content of the longest substring

import java.util.*;
public class Main{
    
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        // Judge which of the two strings is longer and which is shorter 
        if (str1.length() <= str2.length()) {
    
            longString(str1, str2);
        } else {
    
            longString(str2, str1);
        }
    }
    
    public static void longString(String str1,String str2){
    
        char[]arr1 = str1.toCharArray();
        char[]arr2 = str2.toCharArray();
        int len1 = arr1.length;
        int len2 = arr2.length;
        // Define the maximum length maxLen , Start subscript start
        int maxLen = 0;// Length of the longest substring 
        int start = 0;// The starting position of the longest substring 
        int[][] maxSubLen = new int[len1+1][len2+1];
        for(int i = 1;i<=len1;i++){
    
            for(int j =1;j<=len2;j++){
    
                // If the first i Characters are the same as j The characters are equal , Then accumulate 
                if(arr1[i-1] == arr2[j-1]){
    
                    maxSubLen[i][j] = maxSubLen[i-1][j-1]+1;
                    // to update 
                    if(maxLen < maxSubLen[i][j]){
    
                        maxLen = maxSubLen[i][j];
                        start = i - maxLen;
                    }
                }
            }
        }
        System.out.println(str1.substring(start,start+maxLen));
        
    }
}

3、 ... and 、 Last

   What I fear most in learning is no gain , In fact, sometimes it's strange to think , If we don't learn, we won't get anything , If we learn , There may be gains , Then why do we cling to the matter of whether there is harvest itself ？ It may be sunk cost , Because I could have chosen to do something else . Then why don't you do it ？ I don't know … Compete with yourself for a meal , Left and right , What can we get, so ？ Where should the question be , Still there . Don't come or go , What moves is ourselves .