题解 | #公共子串计算#

用压缩数组节省空间，只保留一行，利用动态规划的无后效性。空间复杂度O(N)

#include <algorithm>
#include <vector>


using namespace std;

int main() {
    string str1,str2;
    
    while(cin>>str1>>str2){
        int m =str1.size();
        int n =str2.size();
        vector<int> dp(n+1,0);
        for(int i =0;i<n+1;i++){
            dp[i]=0;
        }
        int temp,left_up,maxlen=-1;
        for(int i =1;i<m+1;i++){
            left_up = dp[0];//保留左上，这个一行的第一个元素
            for(int j =1;j<n+1;j++){
                temp = dp[j];//保留更新过程中的左上
                if(str1[i-1]==str2[j-1]) dp[j]=left_up+1;
                else dp[j]=0;
                left_up = temp;
                if(dp[j]>maxlen)maxlen=dp[j];
            }
            
        }
        cout<<maxlen<<endl;
    }
}