题解 | #最长公共子串#动态规划：只用行数为2的二维数组即可完成

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.size();
        int n = s2.size();
        int max_len = 0;
        int pos = 0;
        string max_result = "";
        //f[i][j]表示以s1[i]、s2[j]结尾的且包含二者的最长字符串长度
        vector<vector<int>>f(2, vector<int>(n+1,0));//由于本行的值只跟上一行和本行的值有关，因此只需两行数组即可存储完成，大大降低内存
        //f[0][]=0 f[][0] = 0
        for(int i = 1; i <=m; ++i){
            for(int j = 1; j <=n; ++j){
                if(s1[i-1] == s2[j-1]){
                    f[1][j] = f[0][j-1] + 1;
                    if(max_len < f[1][j]){
                        max_len = f[1][j];
                        pos = i-1;
                    }
                }
                else{
                    f[1][j] = 0;
                }
                f[0][j-1] = f[1][j-1];
            }
            f[0][n] = f[1][n];
        }
        
        return s1.substr(pos - max_len + 1, max_len);
    }
};

class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, World!"); 
    }
}

print('Hello world!')