上机算法刷题暑期篇(一) —— AcWing 3692. 最长连续公共子序列(西电)

题目链接

AcWing 3692. 最长连续公共子序列

题目详情

题目解析

我们一看到题目,最长和连续子串，我们第一反应应该是什么?没错,就是dp,一般来说，子串问题常见的解法有两种：

• 双指针

• dp
  这道题无疑就是一道最常见的dp问题，而dp问题最重要的无疑就是状态转移了，而在这道题中，我们假设s1字符串的i位置与s2字符串的j位置匹配成功,我们这时就可以有两种选择：

• 将这个匹配结果纳入总结果中，即为：
  $$dp[i][j]=dp[i-1][j-1]+1$$

• 不采用这个结果，即为：
  $$dp[i][j]=d[i-1][j]$$

所以最后的状态转换方程为:
$$dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j])$$

同时，如果dp[i][j]>res，我们就要更新res,同时由于i为外层循环，所以i的位置就是子字符串最后一位字母的位置，所以我们能得到最后的代码：

#include<iostream>
#include<cstring>using namespace std;const int N = 110;
int dp[N][N];
char a[N],b[N];int main()
{memset(dp, 0, sizeof(dp));int res = 0;int index=0; //记录最长公共子串的起始位置string resstr;scanf("%s %s",a+1,b+1);int l1=strlen(a+1),l2=strlen(b+1);for (int i = 1; i <=l1; i++)for (int j = 1; j <= l2; j++){if (a[i] == b[j]){dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i-1][j]);}if (dp[i][j]>=res){res = dp[i][j];index = i - res + 1;}}for (int i = index; i < index + res; i++){resstr += a[i];}cout << res << endl << resstr;return 0;
}

拓展;go语言的解题代码

package mainimport ("fmt""math"
)const N = 110func countEnglishLetters(data []byte) int {count := 0for _, b := range data {if (b >= 'A' && b <= 'Z') || (b >= 'a' && b <= 'z') {count++}}return count
}func main() {dp := make([][]int, N)for i := range dp {dp[i] = make([]int, N)}// 预留足够的空间a := make([]byte, N)b := make([]byte, N)var aRaw, bRaw string_, _ = fmt.Scan(&aRaw, &bRaw) // 读取输入的字符串copy(a[1:], []byte(aRaw)) // 复制到 a 的第1个位置开始copy(b[1:], []byte(bRaw)) // 复制到 b 的第1个位置开始l1:=countEnglishLetters(a)+1l2:=countEnglishLetters(b)+1res := 0index := 0 // 记录最长公共子串的起始位置var resStr stringfor i := 1; i <= l1; i++ {for j := 1; j <= l2; j++ {if a[i] == b[j] {dp[i][j] = int(math.Max(float64(dp[i-1][j-1])+1, float64(dp[i-1][j])))} if dp[i][j] >= res {res = dp[i][j]index = i - res +1}}}for i := index; i < index+res; i++ {resStr += string(a[i])}fmt.Println(res)fmt.Println(resStr)
}