P1730 最长连续公共子序列 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2026年3月22日 21:15

最长连续公共子序列题解：

P1730

回复 0 | 赞 0 | 浏览 38

#include<bits/stdc++.h> using namespace std; int main() { char s0[110],s1[110]; while(scanf("%s %s",s0,s1)!=EOF) { int l0=strlen(s0); int l1...

2026年3月20日 20:05

为什么只有66的通过率，我感觉我的思路没问题，有大神可以讲一下吗

P1730

回复 1 | 赞 5 | 浏览 92

#include<bits/stdc++.h> using namespace std; int main(){ string s1,s2; while(cin>>s1>>s2){ int len1=s1.size(); int len2=s2.size(); &n...

2026年3月18日 11:42

最长连续公共子序列题解：dp[i][j]>=maxx

P1730

回复 0 | 赞 7 | 浏览 80

#include <iostream> #include <cstring> #include <string> using namespace std; int main() { string s1, s2; int dp[101][101]; while (cin >> s1 >> s2) { int l1=s1.size(),l2=s2.size(); memset(dp,0,sizeof(dp)); int maxx=0,pos=0; for(int i=1;i&...

2026年3月14日 16:45

最长连续公共子序列 C语言题解：利用二维数组动态规划

P1730

回复 0 | 赞 5 | 浏览 109

#include <stdio.h> #define MAX 101 int main() { char str1[MAX],str2[MAX]; int len1,len2; while(scanf("%s %s",str1,str2)!=EOF){ //获取长度（可替换为string.h里的strlen函数） for(len1=0;str1...

2026年3月8日 18:53

最长连续公共子序列题解：dp解法查找连续子串

P1730

回复 0 | 赞 15 | 浏览 182

#include <bits/stdc++.h> using namespace std; int main () { string s; while (getline(cin, s)) { int pos = s.find(' '); string s1 = s.substr(0, pos); string s2 = s.substr(pos + 1); int len1 = s1.length(); int len2 = s2.length(); ...

2026年2月12日 18:03

最长连续公共子序列题解：

P1730

回复 0 | 赞 11 | 浏览 287

#include<bits/stdc++.h> using namespace std; int dp[105][105]; int main(){ string a, b; while(cin >> a >> b){ int la = a.size(); int lb = b.size(); // 初始化dp数组为0 memset(dp, 0, sizeof(dp)); int maxLen...

2025年8月19日 14:49

最长连续公共子序列(dp解法) 题解：

P1730

回复 0 | 赞 27 | 浏览 950

dp[i][j]表示以a[i]和b[i]结尾的最长连续公共子序列长度，要求a[i]与b[i]必须为最长连续公共子序列的结尾，否则dp=0 #include<bits/stdc++.h> using namespace std; int dp[1000 + 5][1000 + 5]; int main(){ string a, b; while(cin >> a >> b){ int lena = a.size(); int lenb = b.size(); ...

2025年3月23日 22:34

最长连续公共子序列题解：暴力，找不到最后一个，那就反过来找第一个

P1730

回复 0 | 赞 7 | 浏览 1.1k

#include<bits/stdc++.h> using namespace std; int main() { string str1,str2; while(cin>>str1>>str2) { reverse(str1.begin(),str1.end()); r...

2025年3月20日 21:12

最长连续公共子序列（哈希表、二分法）

P1730

回复 0 | 赞 2 | 浏览 1.2k

最长连续公共子序列注：题目描述中提到的“如果有多个相同长度的子串符合要求，输出最后一个”，表述不够准确。此处应理解为在 s1 中靠后的那个子串。解题思路若两个字符串的最长连续公共子序列长度为n，删去其中的一些字符，我们总能得到长度为 n - k (k >= 0)的连续公共子序列。这体现出典型的二分性质，因此，我们使用二分法猜测公共子序列的长度。至于如何判断是否存在长度为m的子序列，可以将s2中所有长度为m的连续子序列加入哈希表中，并从后往前枚举s1的长度为m的连续子序列，判断其是否在哈希表中即可。因此判断子序列的时间复杂度为O(...

2025年3月14日 11:50

最长连续公共子序列题解：滑动窗口解法

P1730

回复 1 | 赞 8 | 浏览 1.1k

#include <bits/stdc++.h> using namespace std; int main() { string s1, s2; while (cin >> s1 >> s2) { int maxLen = 0; string longestSubstr; for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); ...

1
2

题目最长连续公共子序列

题解数量17

发布题解在线答疑

热门题解

1 dp

2 最长连续公共子序列(dp解法) 题解：

3 换个思路或许更方便

4 最长连续公共子序列题解：dp解法查找连续子串

5 最长连续公共子序列题解：

6 最长连续公共子序列题解：

7 最长连续公共子序列题解：Output Limit Exceeded

8 最长连续公共子序列题解：滑动窗口解法

9 c++暴力

10 最长连续公共子序列题解：暴力，找不到最后一个，那就反过来找第一个