[关闭]
@myecho 2019-04-08T14:25:07.000000Z 字数 7210 阅读 798

字符串dp

动态规划

首先要分清子序列和子串的区别。

  1. 最长递增子序列
  1. #include <iostream>
  2. #include <vector>
  4. using namespace std;
  5. int dp[31];
  6. int lis;
  8. int LIS(int * arr, int size) {
  9.     for (int i = 0; i < size; ++i) {
  10.         dp[i] = 1;
  11.         for (int j = 0; j < i; ++j) {
  12.             if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
  13.                 dp[i] = dp[j] + 1;
  14.                 if (dp[i] > lis) {
  15.                     lis = dp[i];
  16.                 }
  17.             }
  18.         }
  19.     }
  20.     return lis;
  21. }
  23. /*当路径不唯一时，打印的是重复的靠后的*/
  24. void outputLIS(int * arr, int index) {
  25.     bool isLIS = 0;
  26.     if (index < 0 || lis == 0) {
  27.         return;
  28.     }
  29.     if (dp[index] == lis) {
  30.         --lis;
  31.         isLIS = 1;
  32.     }
  33.     outputLIS(arr,--index);
  34.     if (isLIS) {
  35.         printf("%d ", arr[index+1]);
  36.     }
  37. }
  39. int main() {
  40.     int arr[] = {1, -1, -2, -3, 4, -5, 6, -7};
  41.     printf("%d\n", LIS(arr, 8));
  42.     outputLIS(arr, 7);
  43.     return 0;
  44. }
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> ans;

/*
ans[i]表示最长子序列长度为i的结尾元素，这种情况下无法保存路径
O(nlogn)
*/
int LIS(vector<int> & nums) {
    int len = 0;
    for (int i = 0; i < nums.size(); ++i) {
        vector<int>:: iterator it = upper_bound(ans.begin(), ans.end(), nums[i]);
        if (it == ans.end()) {
            ans.push_back(nums[i]);
            len++;
        } else {
            // 能够这样更新的原理实际上是由于可以和前边的构成一个同样长度同时结尾更小的序列
            ans[it-ans.begin()] = nums[i];
        }
    }
    return len; 
}

int main() {
    int arr[] = {1, -1, -2, -3, 4, -5, 6, -7};
    vector<int> nums(arr, arr+8);
    cout << LIS(nums) << endl;
}
  1. 最长公共子序列
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int c[100][100];
  6. int path[100][100];
  8. int LCS(string str1, string str2) {
  9.     int l1 = str1.size(), l2 = str2.size();
  10.     for (int i = 0; i <= l1; ++i) c[i][0] = 0;
  11.     for (int i = 0; i <= l2; ++i) c[0][i] = 0;
  12.     for (int i = 1; i <= l1; ++i) {
  13.         for (int j = 1; j <= l2; ++j) {
  14.             if (str1[i-1] == str2[j-1]) {
  15.                 c[i][j] = c[i-1][j-1] + 1;
  16.                 path[i][j] = 1;
  17.             } else if (c[i-1][j] < c[i][j-1]) {
  18.                 c[i][j] = c[i][j-1];
  19.                 path[i][j] = 2;
  20.             } else {
  21.                 c[i][j] = c[i-1][j];
  22.                 path[i][j] = 3;
  23.             }
  24.         }
  25.     }
  26.     return c[l1][l2];
  27. }
  29. void PrintLCS(string str, int l1, int l2) {
  30.     if (l1 < 0 || l2 < 0) return;
  31.     if (path[l1][l2] == 1) {
  32.         PrintLCS(str, l1-1, l2-1);
  33.         printf("%c ", str[l1]); //回溯的时候才输出
  34.     } else if (path[l1][l2] == 2) {
  35.         PrintLCS(str, l1, l2-1);
  36.     } else {
  37.         PrintLCS(str, l1-1, l2);
  38.     }
  39. }
  41. /*
  42. 优化，不用保存路径时，利用滚动数组
  43. for(i = 1; i <= xlen; ++i)
  44. {
  45.         k = i & 1; //0与1交替
  46.         for(j = 1; j <= ylen; ++j)
  47.         {
  48.             if(X[i-1] == Y[j-1])
  49.             {
  50.                 dp[k][j] = dp[k^1][j-1] + 1; //k^1是取上次的那个
  51.             }else if(dp[k][j-1] > dp[k^1][j])
  52.             {
  53.                 dp[k][j] = dp[k][j-1];
  54.             }else
  55.             {
  56.                 dp[k][j] = dp[k^1][j];
  57.             }
  58.         }
  59.     }
  60. */
  61. int main() {
  62.     string str1 = "cnblog";
  63.     string str2 = "belong";
  64.     printf("%d\n", LCS(str1, str2));
  65.     PrintLCS(str1, str1.size()-1, str2.size()-1);
  66.     return 0;
  67. }

LeetCode的一个类似题目
115. Distinct Subsequences

  1. 最长公共子串
  1. #include <iostream>
  2. using namespace std;
  4. /*
  5. 求两个字符串的最长公共子串，思路DP,可以考虑通过后缀数组优化
  6. 优化思路:
  7. 由于后缀数组最典型的是寻找一个字符串的重复子串，所以，对于两个字符串，我们可以将其连接到一起，如果某一个子串 s 是它们的公共子串，则 s 一定会在连接后字符串后缀数组中出现两次，
  8. 这样就将最长公共子串转成最长重复子串的问题了，这里的后缀数组我们使用基本的实现方式。
  10. 值得一提的是，在找到两个重复子串时，不一定就是 X 与 Y 的公共子串，也可能是 X 或 Y 的自身重复子串，故在连接时候我们在 X 后面插入一个特殊字符‘#’，即连接后为 X#Y。
  11. 这样一来，只有找到的两个重复子串恰好有一个在 #的前面，这两个重复子串才是 X 与 Y 的公共子串
  12. 在判断的时候加一些判断条件方可。
  13. 不过感觉还不如这个快啊。。。o((n+m)^2)
  14. */
  15. int c[100][100];
  16. int maxlen = 0;
  17. int maxindex = 0;
  18. int LCSstring(string str1, string str2) {
  19.     int l1 = str1.size(), l2 = str2.size();
  20.     for (int i = 0; i <= l1; ++i) c[i][0] = 0;
  21.     for (int i = 0; i <= l2; ++i) c[0][i] = 0;
  22.     for (int i = 1; i <= l1; ++i) { //同2中需要注意的点
  23.         for (int j = 1; j <= l2; ++j) {
  24.             if (str1[i-1] == str2[j-1]) {
  25.                 c[i][j] = c[i-1][j-1] + 1;
  26.                 if (maxlen < c[i][j]) {
  27.                     maxlen = c[i][j];
  28.                     maxindex = i - maxlen - 1;
  29.                 }
  30.             } else {
  31.                 c[i][j] = 0;
  32.             }
  33.         }
  34.     }
  35.     return maxlen;
  36. }
  38. void PinrtLCS(string str) {
  39.     for (int i = maxindex+1; i <= maxindex+maxlen; ++i) {
  40.         cout << str[i] << ' ';
  41.     }
  42.     cout << endl;
  43. }
  45. int main() {
  46.     string str1 = "acbac";
  47.     string str2 = "acaccbabb";
  48.     printf("%d\n", LCSstring(str1, str2));
  49.     PinrtLCS(str1);
  50.     return 0;
  51. }
  1. LRS最长可重复子串
    例如： banana 可以重复的最长子串是 ana
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  6. /*最长可重复字串->后缀数组基础应用*/
  7. vector<string>postfix;
  8. int maxlen  = 0;
  10. int comlen(string str1, string str2) {
  11.     int i = 0, j = 0;
  12.     int l1 = str1.size(), l2 = str2.size();
  13.     int len = 0;
  14.     while (i < l1 && j < l2 && str1[i++] == str2[j++]) {
  15.         len++;
  16.     }
  17.     return len;
  18. }
  20. int LRS(string str) {
  21.     for(int i = 0; i < str.size(); ++i) {
  22.         postfix.push_back(str.substr(i));
  23.     }
  24.     sort(postfix.begin(), postfix.end());
  25.     for (int i = 0; i < postfix.size()-1; ++i) {
  26.         int len = comlen(postfix[i], postfix[i+1]);//只需比较相邻的后缀
  27.         if (maxlen < len) maxlen = len;
  28.     }
  29.     return maxlen;
  30. }
  32. //O(n^3)的基础算法 两个循环枚举两个后缀的开头~ 使用后缀数组后优化到O(N^2)
  33. 这里的重复子串是允许重叠的
  34. void LRS_base(char * arr, int size)
  35. {
  36.     for(int i = 0; i < size; ++i)
  37.     {
  38.         for(int j = i+1; j < size; ++j)
  39.         {
  40.             int len​​ = comlen(&arr[i],&arr[j]);
  41.             if(len > maxlen)
  42.             {
  43.                 maxlen = len;
  44.                 maxindex = i;
  45.             }
  46.         }
  47.     }
  48. }
  50. int main() {
  51.     string str = "banana";
  52.     cout << LRS(str) << endl;
  53.     return 0;
  54. }

九度OJ 1555重复子串->不允许重叠
0(n^2)的直接枚举,也可以使用后缀数组继续优化能够达到o(nlogn)的复杂度

  1.     while(cin >> s)
  2.     {
  3.         int L = s.size();
  4.         int i , j ;
  5.         int len ; 
  6.         set<string> ans;
  7.         for(i = 0; i < L; i++)
  8.         {
  9.             for(len = 1; len + len + i <= L; len++) // 右边的字符串要长于左边的字符串
  10.             {
  11.                 string left = s.substr(i,len);
  12.                 string right = s.substr(i+len);
  13.                 if(right.find(left) != string::npos)
  14.                     ans.insert(left);   
  15.                 else
  16.                     break;
  17.             }
  18.         }
  19.         printf("%d\n",(int)ans.size());//输出符合条件的子串个数
  20.     }

关于后缀数组还有很多更深的发展，详见<算法>第4版所提到的知识点

  1. 关于回文串相关
    5.1 普通的回文子串
  1. #include <iostream>
  2. using namespace std;
  3. /*最长回文子串*/
  4. bool p[100][100];
  5. //空间复杂度是O(N^2) //好处是每次需要判断某段区间是否为回文串时可以直接访问数组即可
  6. string longestPalindrome(string str) {
  7.     int n = str.size();
  8.     int begin = 0;
  9.     int maxlen = 1;
  10.     for (int i = 0; i < n; ++i) p[i][i] = true;
  11.     //当p(i,i+1)时会递归到p(i+1,i)处理好边界，防止这种情况出现或者设置p(i+1,i)的值
  12.     for (int i = 0; i < n - 1; ++i) p[i][i+1] = str[i] == str[i+1]? true:false;
  13.     for (int i = n-1; i >= 0; --i) {   //j > i
  14.         for (int j = i+2; j < n; ++j) {
  15.             if (str[i] == str[j] && p[i+1][j-1]) {
  16.                 begin = i;
  17.                 maxlen = j - i + 1;
  18.                 p[i][j] = true;
  19.             }
  20.         }
  21.     }
  22.     return str.substr(begin, maxlen);
  23. }
  24. //中心拓展的方式 空间复杂度降到了O(1)
  25. string expand(string s, int c1, int c2) {
  26.     int l = c1, r = c2;
  27.     int n = s.size();
  28.     while (l >= 0 && r <= n -1 && s[l--] == s[r++]);
  29.     return s.substr(l+1, r-l-1);
  30. }
  32. string longestPalindrome1(string s) {
  33.     int n = s.size();
  34.     string longest = s.substr(0,1);
  35.     if (n == 0) return "";
  36.     for (int i = 0; i < n-1; ++i) {
  37.         string p1 = expand(s, i, i);
  38.         if (p1.size() > longest.size()) longest = p1;
  39.         string p2 = expand(s, i, i+1);
  40.         if (p2.size() > longest.size()) longest = p2;
  41.     }
  42.     return longest;
  43. }
  44. //传说中的Manacher算法。时间复杂度O(N)
  45. https://segmentfault.com/a/1190000003914228
  46. int main() {
  47.     string str = "cabbac";
  48.     cout << longestPalindrome(str) << endl;
  49.     return 0;
  50. }

5.2 最长回文子序列

  1. #include <iostream>
  2. #include <algorithm>
  4. using namespace std;
  5. int dp[100][100];
  6. /*求最长的回文子序列*/
  7. int longestPalindrome(string s) {
  8.     int n = s.size();
  9.     for (int i = 0; i < n; ++i) dp[i][i] = 1;
  10.     for (int i = 0; i < n - 1; ++i) dp[i][i+1] = s[i] == s[i+1]?2:1;
  11.     for (int i = n - 1; i >= 0; --i) {
  12.         for (int j = i + 2; j < n; ++j) { // j > i
  13.             if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1]+2;
  14.             else dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
  15.         }
  16.     }
  17.     return dp[0][n-1]; //注意这里只有一个字符串
  18. }
  20. int main() {
  21.     string str = "abcfgbda";
  22.     cout << longestPalindrome(str) << endl;
  23.     return 0;
  24. }

5.3 求解最少需要添加多少字符可以组合成回文串
本质还是求解LCS(最长公共子串)，然后用s-LCS(s与s的反串)即为所求
http://www.cnblogs.com/huzhenbo113/p/3242779.html
最长公共子串，不是最长公共子序列

  1. question:求解一个序列的最长等差数列的问题
    思路:
    子序列的处理:
  2. dp 需要有序,不排序可能会产生负数
    1.1 (这种方式无序也可以)如果差值特别大的情况下 用dp[i][j]表示以a[i]和a[j]结尾的等差序列的长度，dp[i][j] = max(dp[k][i],a[i] - a[k] == a[j] - a[i])+1，边界dp[0,j]=2；dp[0,0]=1;
    1.2 (需要有序)如果差值d不是很大，用dp[i][d]表示以a[i]结尾的差为d的等差序列的长度,dp[i][d] = max{dp[k][d],a[i]-a[k]=d}+1，dp[0,d]=1 不是很好的方法
  3. hash(不需要有序，以差为key, (i,j)为value)，再扫一遍hash表合并(i,j)即可
  4. 类似回文子序列的方式，当符合等差的规则才由dp[i+1,j-1]向dp[i,j]拓展，dp处理
    子串的处理方式:
    子串处理起来比较简单,也不需要有序
    if A[i]-A[i-1]=A[i-1]-A[i-2] S[i]=S[i-1]+1 else S[i] = 2

答案的获取都是需要最后再扫一遍，或者在过程中利用全局变量进行保存。
补充:
关于1.1 本来是o(N^3)
有两种方式可以降到:
1. 利用等差序列的性质 优化内层循环 当j增大时，p也必须随着增大(必须当有序时，因此p不必重新开始)
http://www.1point3acres.com/bbs/thread-14078-1-1.html
2. 利用数据结构(如hash等)，加快a[p]的寻找

leetcode 97. Interleaving String
题意很简答，就是问一下字符串可以不可以通过两个字符串交替出现得到。

dp[i][j]表示0~s1[i]和0~s2[j]可以构成s3的[i+j-1]的字符串

#include<iostream>
#include <vector>

using namespace std;

//当你遇到字符串匹配的时候一般都要想到DP动态规划的做法
class Solution 
{
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        if (s3.length() != s1.length() + s2.length())
            return false;
        vector<vector<bool>> dp(s1.length()+1,vector<bool>(s2.length()+1,0));
        dp[0][0] = true;
        for (int i = 1; i <= s1.length(); i++)
        {
            if (s1[i-1] == s3[i-1] && dp[i - 1][0])
                dp[i][0] = true;
        }

        for (int i = 1; i <= s2.length(); i++)
        {
            if (s2[i-1] == s3[i-1] && dp[0][i-1])
                dp[0][i] = true;
        }

        for (int i = 1; i <= s1.length(); i++)
        {
            for (int j = 1; j <= s2.length(); j++)
            {
                if (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j])
                    dp[i][j] = true;

                if (s3[i + j - 1] == s2[j - 1] && dp[i][j-1])
                    dp[i][j] = true;
            }
        }
        return dp[s1.length()][s2.length()];
    }
};
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注