最长公共子串问题空间复杂度为O(1)的解法

图是从左神的书里截的。这个思路很很巧妙。例如当前有如下两个串：
a b c d e
b e b c d
构造图4-10，图中的数值表就是二维dp[i][j]的值。dp[i][j]只与dp[i-1][j-1]有关。每一轮斜线扫描时，开始长度curLen = 0，如果对应i, j的字符相等，则curLen++，不同则又将curLen重置为0。相当于用curLen来代替dp[i][j]，省下了O(m*n)的空间。

#include <string>
#include <iostream>
using namespace std;
string commonStr(string& s1, string& s2) {
    int n1 = s1.size();
    int n2 = s2.size();
    int starti = n1 - 1; //第一个字符串最后一个字符串开始
    int startj = 0;   //第二个字符串第1个字符开始，
    int targeti = -1; //最长公共子串在s1上的结束位置
    int maxLen = 0;//最长公共子串的长度
    int curLen = 0; //每一轮扫描时的实时公共子串最大长度
    while(startj < n2) {
        curLen = 0;
        for(int i = starti, j = startj; i < n1 && j < n2; i++, j++) {//从左往右按图4-10扫描斜线
            if(s1[i] == s2[j]) {//相同，则沿着斜线往右下走
                curLen++;
                if(curLen > maxLen) {//发现更长的子串，记录下来
                    maxLen = curLen;
                    targeti = i;
                }
            }
            else {//不同，则重置
                curLen = 0;
            }
        }
        if(starti > 0) {//行从n1-1变到0之后，不变
            starti--;
        }
        else {//行到0后，列的开始位置逐轮递增
            startj++;
        }
    }
    return maxLen == 0 ? "-1" : s1.substr(targeti - maxLen + 1, maxLen);
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << commonStr(s1, s2) << endl;
    return 0;
}