最长公共子串（子序列）、最长递增子序列、最长回文子串等问题_最长递增子序列lis、最大连续子序列和、最大连续子序列乘积

最长公共子串

定义

和最长公共子序列不同的是，最长公共子串必须连续。
字符串 “abcdea”和“aebcda”如果都以最左端的a字符对齐，则能够匹配的最长公共子串就是“a”。但是如果用第二个字符串的e字符对齐第一个字符串的a字符，则能够匹配的最长公共子串就是“bcd”。可见，从两个字符串的不同位置开始对齐匹配，可以得到不同的结果，因此，本文采用的算法就是穷举两个字符串所有可能的对齐方式，对每种对齐方式进行字符的逐个匹配，找出最长的匹配子串。

动态规划

同样采用一个二维矩阵c[i][j]来记录中间的结果。循环遍历两个字符串,查找当s1[i]==s2[k] 的情况 然后保存在c[i][k]中，c[i][k]=c[i-1][k-1]+1 最后我们会得到类似以下矩阵：

int LongestSubstring(string s1,string s2) {
    int len1 = s1.size();
    int len2 = s2.size();
    if(len1 == 0 || len2 == 0) 
        return -1;
    //保存最长公共子串的长度
    int ans = 0;
    vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
    for(int i=1;i<=len1;i++) 
    {
        for(int j=1;j<=len2;j++) 
        {
            if (s1[i-1] == s2[j-1]) 
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                ans = max(ans,dp[i][j]);
            }
        }
    }
    return ans;
}

int main(void) {
    string a="abcgooglecba";
    string b="cbagoogleABVC";
    cout<<LongestSubstring(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

最长公共子序列

最长公共子序列的问题常用于解决字符串的相似度，是一个非常实用的算法。

定义

一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称S为已知序列的最长公共子序列。
子序列不要求连续，可以是原序列中删除若干元素后得到的序列。
求解子序列是非连续的最长公共子序列问题是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。

动态规划

利用dp[i][j]计算长度，利用r[i][j]记录查找LCS的过程。

• 第一步：先计算最长公共子序列的长度。
• 第二步：根据长度，然后通过回溯求出最长公共子序列。

计算最长公共子序列的长度

现有两个序列X={x1,x2,x3，…xi}，Y={y1,y2,y3，….，yi}，
设一个dp[i][j]保存Xi与Yj的LCS的长度。
递推方程为：

引进一个二维数组dp[][]，用dp[i][j]记录X[i]与Y[j] 的LCS 的长度，r[i][j]记录dp[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算dp[i][j]之前，dp[i-1][j-1]，dp[i-1][j]与dp[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。

如果只要求字符串A和B的最长公共子序列的长度，那么代码实现为：
注意到和上面的最长公共子串不同，这里不需要辅助变量ans，因为dp[n][m]里保存的就是所求的答案了。

class LCS {
public:
    int findLCS(string A, string B) {
        int n = A.size();
        int m = B.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        //int ans = 0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(A[i-1] == B[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                //ans = max(ans,dp[i][j]);
            }
        return dp[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

反求最长公共子序列

dp[n][m]只是最长公共子序列的长度值，表示了两个字符串的相似程度，如果要获得最长公共子序列，就需要在计算出dp[n][m]矩阵的值后分析每一步决策的结果，根据每一个最优决策逆向构造出最长公共子序列。
为此需要在递推计算dp[i,j]的过程中，同时记录下最优决策的过程，最优决策的过程用矩阵r表示，r[i][j]表示最长公共子序列的长度值dp[i][j]的“递推来源”。根据前面整理的递推关系：

• 如果r[i][j]的值是1，则表示dp[i][j]的值由dp[i-1][j-1] + 1递推得到；
• 如果r[i][j]的值是2，则表示dp[i][j]的值由dp[i-1][j]递推得到；
• 如果r[i][j]的值是3，则表示dp[i][j]的值由dp[i][j-1]递推得到。

以字符串“abcdea”和“aebcda”为例，根据递推关系得到的d和r合并到一个矩阵中显示：

那么获得该最长公共子序列的过程就是一个从dp[n][m]逆推到dp[1][1]的过程了。

最长递增子序列

要找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。
例如，{10，22，9，33，21，50，41，60，80} 的LIS的长度是6，该 LIS是{10，22，33，50，60，80}。
思路1：
仿照最长公共子序列。
将已知序列A排序，得到序列B，求A和B的最长公共子序列，即是求A的最长递增子序列。但该方法的时间复杂度比较高。
思路2：
对于长度为N的数组A[N] = {a0, a1, a2, …, an-1}，假设我们想求以ai结尾的最大递增子序列长度，设为dp[i]。我们需要遍历ai前面的元素aj（j = 0~i-1），如果aj

int temp = 0;
for(int j=0;j<i;j++)
    if(A[j]<A[i])
        temp = max(temp,dp[j]);
dp[i] = temp + 1;
1
2
3
4
5

然后，对每一个A[i]都计算以它结尾的最大递增子序列的长度dp[]，dp[]中的最大值即为所求。
该方法的时间复杂度为O(n^2)。

完整的实现如下：

class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;

        int ans = 1;

        for(int i=1;i<n;i++)
        {
            int temp = 0;
            for(int j=0;j<i;j++)
                if(A[j]<A[i])
                    temp = max(temp,dp[j]);
            //求以A[i]结尾的子序列的最大值
            dp[i] = temp + 1;
            //从dp[]中找总的最大值
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路3：
贪心+二分查找：（O(nlogn)）
开辟一个栈，每次取栈顶元素s和读到的元素a做比较，如果a>s， 则加入栈；如果a<s，则二分查找栈中的比a大的第1个数，并替换。 最后序列长度为栈的长度。
这也是很好理解的，对x和y，如果x

class Solution {
public:
    //用来存放最大递增子序列的结果，可以看做是一个栈
    vector<int> sub;

    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len<=1) return len;

        sub.push_back(nums[0]);

        for(int i=1;i<len;i++)
        {
            //如果nums[i]大于栈顶元素，就入栈
            if(nums[i]>sub[sub.size()-1])
                sub.push_back(nums[i]);
            else
            {
                //定位到sub中第一个大于等于nums[i]的数的位置，并替换它
                int k=BinarySearch(nums[i]);
                //用nums[i]把sub[k]替换掉
                sub[k]=nums[i];
            }
        }
    return sub.size();
    }

    //返回arr中，大于c的第一个数
    int BinarySearch(int c)
    {
        int low=0,high=sub.size()-1;

        while(low<=high)
        {
            int mid=(low+high)>>1;
            //如果找到了与c相等的，也要直接返回
            if(c==sub[mid])
                return mid;
            //找到大于c的最小值
            else if(c>sub[mid])
                low=mid+1;
            else
                high=mid-1;
        }
        return low;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

最大连续子序列和

简单的动态规划。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int length=nums.size();
        if(length==0)   return 0;

        int dp[length]={0};
        dp[0]=nums[0];
        int ans=nums[0];

        for(int i=1;i<length;i++)
        {
            if(dp[i-1]<0)
                dp[i] = nums[i];
            else 
                dp[i] = nums[i] + dp[i-1];
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最大连续子序列乘积

考虑到数可以是正负的，所以最大的乘积可能是由两个负数相乘得到的。因此，在解题过程中要开2个数组，分别保存目前为止最大的乘积和最小的乘积。具体见代码：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        if (len == 0)
            return 0;

        vector<int> dpMax(len);
        vector<int> dpMin(len);
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];

        int ans = nums[0];

        for (int i = 1; i < len; i++){
            int tmp1 = dpMin[i - 1] * nums[i];
            int tmp2 = dpMax[i - 1] * nums[i];
            //三者的最小值
            dpMin[i] = min(min(tmp1, tmp2), nums[i]);
            //三者的最大值
            dpMax[i] = max(max(tmp1, tmp2), nums[i]);

            ans = max(ans,dpMax[i]);
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

最长回文子串

首先说一个错误的思路：将原字符串s1反转成s2，然后转换成求s1和s2的最长公共子串问题。但这样是不行的，反例：S=”abacdfgdcaba”，若按这种解法得到答案是：”abacd”，显然不是回文，而正确答案是”aba”。

最朴素的暴力法是遍历字符串S的每一个子串，去判断这个子串是不是回文，是回文的话看看长度是不是比最大的长度maxlength大。遍历每一个子串的方法要O（N2），判断每一个子串是不是回文的时间复杂度是O(N)，所以暴利方法的总时间复杂度是O（N3）。

下面介绍两种方法，第一种中心拓展法较为推荐，而第二种Manacher法较为复杂…不太容易实现。
思路1：
中心扩展法
时间复杂度为O（N2），空间复杂度仅为O（1）。就是对给定的字符串S，分别以该字符串S中的每一个字符C为中心，向两边扩展，记录下以字符C为中心的回文子串的长度。但是有一点需要注意的是，回文的情况可能是 a b a，也可能是 a b b a。所以对每一个s[i]，都要分别计算以它为中心的奇数回文串和偶数回文串，并从中选一个较长的。

完整代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0) return s;

        //初始化为第一个字符
        string longest = s.substr(0,1);

        for (int i = 0; i < n-1; i++) 
        {
            //以i为中心的奇数回文子串
            string p1 = expandAroundCenter(s, i, i);
            if (p1.length() > longest.length())
                longest = p1;
            //以i和i+1为中心的偶数回文子串
            string p2 = expandAroundCenter(s, i, i+1);
            if (p2.length() > longest.length())
                longest = p2;
        }
        return longest;
    }

    string expandAroundCenter(string s, int left, int right) {
        int n = s.length();
        while (left >= 0 && right < n && s[left] == s[right]) 
        {
            left--;
            right++;
        }
        return s.substr(left+1, right-left-1);
    }    

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

思路2：
Manacher法。
求回文串时需要判断其奇偶性，也就是求aba 和abba 的算法略有差距。然而，这个算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能在原串中出现，一般可以用‘#’或者‘$’等字符。例如：
原串：abaab
新串：#a#b#a#a#b#
这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心奇数回文串了。
接下来就是算法的中心思想，用一个辅助数组P 记录以每个字符为中心的最长回文半径，也就是P[i]记录以Str[i]字符为中心的最长回文串半径。P[i]最小为1，此时回文串为Str[i]本身。
我们可以对上述例子写出其P 数组，如下
新串： # a # b # a # a # b #
P[] : 1 2 1 4 1 2 5 2 1 2 1
我们可以证明P[i]-1就是以Str[i]为中心的回文串在原串当中的长度。

class Solution {
public:
    string longestPalindrome(string s) {
        const int len = s.size();
        if(len <= 1)return s;
        //Manncher算法 ，o（n）
        string str = preProcess(s);
        int n = str.size(), id = 0, mx = 0;
        vector<int>p(n, 0);
        for(int i = 1; i < n-1; i++)
        {
            p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
            //if(mx <= i || (mx > i && p[2*id-i] == mx - i)) //根据正文斜体部分的注释，这里可要可不要
            while(str[i+p[i]] == str[i-p[i]])p[i]++;
            if(i + p[i] > mx)
            {
                mx = i + p[i];
                id = i;
            }
        }

        //遍历p，寻找最大回文长度
        int maxLen = 0, index = 0;
        for(int i = 1; i < n-1; i++)
            if(p[i] > maxLen)
            {
                maxLen = p[i];
                index = i;
            }
        return s.substr((index - maxLen)/2, maxLen-1);
    }
    //预处理字符串，abc预处理后变成$#a#b#c#^
    string preProcess(const string &s)
    {
        int n = s.size();
        string res; 
        res.push_back('$');//把$放到字符串头部
        res.push_back('#');//以#作为原来字符串中每个字符的间隔
        for(int i = 0; i < n; i++)
        {
            res.push_back(s[i]);
            res.push_back('#');
        }
        res.push_back('^');//以^作为字符串的结尾
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47