提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

最长公共子序列与最长公共子串

序列 最长 公共 子串
2023-06-13 09:12:45 时间

最长公共子序列

举个例子：s1="abcfde"，s2="bcde"。那么s1与s2的最长公共子序列就是"bcde"，注意不要求连续。该问题是典型的动态规划问题。

(i, j)从0开始，那么递推关系很容易找到：(maxLen(i,j)表示s1字符串左边i个字符构成的子串与s2左边j个字符构成的子串的最长公共子序列长度，下同)

if(s1[i-1] == s2[j-1]) {
    maxLen(i,j) = maxLen(i-1,j-1) + 1;
}else {
    maxLen(i,j) = max(maxLen(i,j-1), maxLen(i-1,j));
}

求最长公共子序列并输出：

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e3;
int flag[MAX+5][MAX+5];
char s1[MAX+5],s2[MAX+5];
int dp[MAX+5][MAX+5];

void LCS() {
    memset(dp,0,sizeof(dp));
    memset(flag,0,sizeof(flag));
    for(int i = 1; i <= strlen(s1); i++) {
        for(int j = 1; j <= strlen(s2); j++) {
            if(s1[i-1] == s2[j-1]) {
              dp[i][j] = dp[i-1][j-1] + 1, flag[i][j] = 0;
      }else if(dp[i-1][j] >= dp[i][j-1]) {
        dp[i][j] = dp[i-1][j], flag[i][j] = 1;
      }else {
        dp[i][j] = dp[i][j-1], flag[i][j] = -1;
      }      
        }
    }
}
void PrintLCS(int i,int j) {
    if(i == 0 || j == 0) {
      return ;
  }
    if(flag[i][j] == 0) {
        PrintLCS(i-1, j-1);
        cout << s1[i-1];
    }
    else if(flag[i][j] == 1) {
      PrintLCS(i-1, j);
  }else {
    PrintLCS(i, j-1);
  }      
}
int main() {
    while(cin >> s1 >> s2) {
        LCS();  
        PrintLCS(strlen(s1), strlen(s2));
        cout << endl;
    }
}

最长公共子串

最长公共子串与上述最长公共子序列不一样，最长公共子串要求连续。

例如s1="asdfddsx"，s2="asssdfed"，那么s1与s2的最长公共子串是："sdf"。最长公共子串的输出比上面最长公共子序列简单，因为后者一定是连续的，我们只要保存最后一个两个字符串字符相等的位置index，以及最长公共子串的长度length，然后从index位置往回倒推index个字符即可。

递推关系为：

if(s1[i-1] == s2[j-1]) {
    maxlen(i, j) = maxLen(i - 1, j - 1) + 1
}

求最长公共子串并输出：

#include<bits/stdc++.h>
using namespace std;

string str1, str2;
int dp[1002][1002], ans=1, index;

int main() {
  cin >> str1 >> str2;
  memset(dp, 0, sizeof(dp));
  int x = str1.length(), y = str2.length();
  for(int i = 1; i <= x; i++) {
    for(int j = 1; j <= y; j++) {
      if(str1[i-1] == str2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
        if(ans <= dp[i][j]) {
          ans = dp[i][j];   //公共子串长度 
          index = i;    //保留当前位置 
        }
      }
    }
  }
  cout << ans << endl;
  for(int i = index - ans; i < index; i++) {
    cout << str1[i];
  }
  return 0;
}

相关文章