Topic describes

Given two strings str1 and str2, print the longest common substring of the two strings, ensuring that the longest common substring of str1 and str2 exists and is unique

The sample

str1 = “1AB2345CD”

str2 = “12345EF”

substr = “2345”

Use dynamic programming to solve

Note that the above description is solving the longest common subsequence, not the longest common subsequence, the subsequence can be discontinuous content, but the substring must be continuous content.

Define dp[I][j] to represent the longest common substring formed by the ith element of string str1 and the JTH element of string 2 being the last element. So if you want to find out whether dp[I][j], the ith element in str1, is equal to the JTH element in str2, if they are equal then you record them and if they are not equal then you don’t record them. This means that dp[I][j]=0. If the equal, the need to compute the equal in front of the characters, is actually dp [I – 1] [1], so dp [I] [j] = dp [I – 1] [1] + 1;

As shown in the figure, the code is relatively simple, for example, we use two variables, one for the longest common substring, and one for the position where the longest common substring ends. Finally, you can just cut the string out of it.

public String LCS(String str1,String str2){
    int maxLenth = 0; // Record the length of the longest common substring
    // Records the position of the last element of the longest common substring in character str1
    int maxLastIndex = 0;
    int[][] dp =  new int[str1.lenght()+1][str2.lenght()+1]
    for(int i = 0; i<str1.length(); i++){for(int j = 0; j<str2.length(); j++){if(str1.charAt(i)==str2.charAt(j)){
                dp[i+1][j+1] = dp[i][j]+1;
                // If a longer substring is encountered, to update, record the length of the longest string
                // And the position of the last element in the string
                if(dp[i+1][j+1]>maxLenth){
                    maxLenth = dp[i+1][j+1]; maxLastIndex = i; }}else{
                // Recursively declare two strings are not equal
                dp[i+1][j+1] = 0; }}}return str1.substring(maxLastIndex-maxLenth+1,maxLastIndex+1)}Copy the code

Time complexity O(m* N)

Space complexity O(m* N)

Code optimization, the two-dimensional array into a one-dimensional array.

public String LCS(String str1,String str2){
    int maxLenth = 0; // Record the length of the longest common substring
    // Records the position of the last element of the longest common substring in character str1
    int maxLastIndex = 0;
    int[] dp = new int[str2.lenght()+1]
    for(int i = 0; i<str1.length(); i++){for(int j = 0; j<str2.length()-1; j++){if(str1.charAt(i)==str2.charAt(j)){
                dp[j+1] = dp[j]+1;
                // If a longer substring is encountered, to update, record the length of the longest string
                // And the position of the last element in the string
                if(dp[j+1]>maxLenth){
                    maxLenth = [j+1]; maxLastIndex = i; }}else{
                // Recursively declare two strings are not equal
                dp[j+1] = 0; }}}return str1.substring(maxLastIndex-maxLenth+1,maxLastIndex+1)}Copy the code

Time complexity O(m* N)

Space complexity O(n)

conclusion

So in this case they want to return the longest common substring, they want to return a string, and in some cases, they just want to return the length of the longest common substring. But if you can compute the length, you can compute the longest common substring. I hope the dynamic programming solution here can provide you with some help.