ACM. Hj75 common substring calculation ●●

HJ75 Common substring calculation ●●

describe

The given two contain only Lowercase letters String , 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\le s\le 150$
Advanced ： Time complexity ：$O(n^3)$, Spatial complexity ：$O(n)$

Input description ：

Enter two strings containing only lowercase letters

Output description ：

Output an integer , Represents the length of the largest common substring

Example

Input ：
asdfas
werasdfaswer
Output ：
6

Answer key

Inherent LC 718. Longest repeating subarray similar .
Solution visible C++ Data structure and algorithm （ 13、 ... and ）（ Dynamic programming – raid homes and plunder houses 、 Stock issues 、 Subsequence problem ）.

1. Dynamic programming

1. dp[i][j] Said to s1[i-1]、s2[j-1] by ending （ These two characters must be included ） The common substring length of the string of （ Not necessarily the biggest ）;
2. Initialize to 0;
3. If s1[i-1] == s2[j-1], that dp[i][j] = dp[i-1][j-1] + 1;, And compare the update maximum length ;
   otherwise , The end of the string is not equal , That is, the common length is 0.
4. Traversing from front to back .

• Time complexity ：$O(n\times m)$,n by A length ,m by B length
• Spatial complexity ：$O(n\times m)$

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    
    string s1, s2;
    while(cin >> s1 >> s2){
    
        int n = s1.length(), m = s2.length(), ans = 0;
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        for(int i = 1; i <= n; ++i){
    
            for(int j = 1; j <= m; ++j){
    
                if(s1[i-1] == s2[j-1]){
    				//  The end of the selected string is equal 
                    dp[i][j] = dp[i-1][j-1] + 1;	//  Last string length  + 1
                    ans = max(ans, dp[i][j]);
                }									// s1[i-1] != s2[j-1]  The ending is different , The length is 0
            }
        }
        cout << ans << endl;
    }
    return 0;
}

• One dimensional rolling array optimizes space complexity O(n)

dp[i][j] It's all by dp[i - 1][j - 1] Introduction . Then compress it into a one-dimensional array , That is to say dp[j] It's all by dp[j - 1] Introduction .

In other words, it is equivalent to that the upper layer dp[i - 1][j] Copy to the next layer dp[i][j] To continue using .

Now traverse B When you have an array , Will be Traverse from back to front , This avoids repeated overwriting , And the length is 0 Pay attention to the assignment .

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    
    string s1, s2;
    while(cin >> s1 >> s2){
    
        int n = s1.length(), m = s2.length(), ans = 0;
        vector<int> dp(m+1, 0);
        for(int i = 1; i <= n; ++i){
    
            for(int j = m; j >= 1; --j){
    
                if(s1[i-1] == s2[j-1]){
    
                    dp[j] = dp[j-1] + 1;	//  equal 
                    ans = max(ans, dp[j]);
                }else{
    
                    dp[j] = 0;				//  It's not equal 
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

2. The sliding window

Iterate through all string overlaps by sliding the string , Then find the length of the largest common substring in the overlapping part .

As shown in figure shows , enumeration character string All overlaps （ alignment ） The method is mainly divided into three steps （s1 Smaller length ）：
（1）s1 The tail starts with s2 overlap , until s1 Completely covered ;
（2）s1 Head and s2 The head begins to dislocate , until s1 The tail And s2 The tail overlaps ;
（3）s1 The tail exceeds s2 The tail , Until there is no overlap .

Each sliding operation needs to update the overlapping start and end subscripts of the two strings .

• Time complexity ： $O((N+M)\times \min (N,M))$
• Spatial complexity ： $O(1)$

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int getLen(string s1, string s2, int a1, int b1, int a2, int b2){
       //  find s1[a1, b1] and s2[a2,b2] Maximum common substring length of 
    int n = b1 - a1 + 1;
    int pre = 0, ans = 0;
    for(int i = 0; i < n; ++i){
    
        if(s1[a1 + i] == s2[a2 + i]){
    
            ans = max(ans, pre + 1);
            ++pre;
        }else{
    
            pre = 0;
        }
    }
    return ans;
}

int main(){
    
    string s1, s2;
    //  The sliding window 
    while(cin >> s1 >> s2){
    
        if(s1.length() > s2.length()) swap(s1, s2);
        int n = s1.length(), m = s2.length(), ans = 0;  // s1  shorter 
        for(int i = 1; i <= n; ++i){
            // s1  The tail starts with  s2  overlap , until  s1  Completely covered 
            int subLen = getLen(s1, s2, n-i, n-1, 0, i-1);
            ans = max(ans, subLen);
        }

        for(int i = 1; i <= m-n; ++i){
          // s1  Head and  s2  The head begins to dislocate , until  s1  The tail   And  s2  The tail overlaps 
            int subLen = getLen(s1, s2, 0, n-1, i, n+i-1);
            ans = max(ans, subLen);
        }

        for(int i = 1; i < n; ++i){
             // s1  The tail exceeds  s2  The tail , Until there is no overlap 
            int subLen = getLen(s1, s2, 0, n-1-i, m-2-n+i, m-1);
            ans = max(ans, subLen);
        }

        cout << ans << endl;
    }
    return 0;
}