[已解决]两个字符串最长子序列问题

ksdeer

描述
阿贝尔，挪威数学家，一生穷困潦倒，他希望以他的才华在皇家科学院谋职以支撑他的生活。他给当时的权威高斯寄去了他的研究成果，但是高斯不希望有人能超过他，不愿意收阿贝尔为徒弟。尽管阿贝尔成就极高，却在生前没有得到认可，他的生活非常贫困，死时只有27岁。就在他死后的第二天，皇家科学院给他寄去了任职信。

阿贝尔定理应用于数列判敛，所以正如你们所料，阿贝尔留下的是两个序列，希望你能计算出最长的公共子序列。

举个例子，cnblogs这个字符串中子序列有多少个呢？很显然有27个，比如其中的cb,cgs等等都是其子序列，我们可以看出子序列不见得一定是连续的，连续的那是子串。

输入
第一行为第一个字符串，第二行为第二个字符串，两个字符串的长度均不超过100

输出
输出这两个字符串的最长的公共子序列

样例输入
cnblogs

belong

样例输出
blog

1. #include <stdio.h>
   
2. #include <string.h>
   
3. int k = 0;
   
4. char yuri[101][101];
   
5. 
   
6. char *str(char *fuck,char *shit,char *temp);
   
7. int main(void)
   
8. {
   
9.     char fuck[101];
   
10.     char shit[101];
    
11.     while(scanf("%s\n%s", fuck,shit) != EOF)
    
12.     {
    
13.         char temp[101];
    
14.         if(strlen(fuck) > strlen(shit))
    
15.         {
    
16.             printf("%s\n", str(fuck,shit,temp));
    
17.         }
    
18.         else
    
19.         {
    
20.             printf("%s\n", str(shit,fuck,temp));
    
21.         }
    
22.         for(int i = 0; i < 101; i++)
    
23.         {
    
24.             for(int j = 0; j < 101; j++)
    
25.             {
    
26.                 yuri[i][j] = '\0';
    
27.             }
    
28.         }
    
29.     }
    
30.     return 0;
    
31. }
    
32. char *str(char *fuck,char *shit, char *temp)
    
33. {
    
34.     int w = 0;
    
35.     int k = 0;
    
36.     int fault = 0;
    
37.     for(int u = 0; u < strlen(shit); u++)
    
38.     {
    
39.         for(int i = u; i < strlen(shit); i++)
    
40.         {
    
41.             for(int j = w; j < strlen(fuck); j++)
    
42.             {
    
43.                 if(shit[i] == fuck[j])
    
44.                 {
    
45.                     temp[k] = shit[i];
    
46.                     k++;
    
47.                     w = j + 1;
    
48.                     break;
    
49.                 }
    
50.             }
    
51.         }
    
52.         temp[k] = '\0';
    
53.         strcpy(yuri[fault],temp);
    
54.         fault++;
    
55.         for(int i = 0; i < k; i++)
    
56.         {
    
57.             temp[i] = '\0';
    
58.         }
    
59.         k = 0;
    
60.         w = 0;
    
61.     }
    
62.     char ttemp[101];
    
63.     for(int i = 0; i < fault - 1; i++)
    
64.     {
    
65.         for(int j = 0; j < fault - 2; j++)
    
66.         {
    
67.             if(strlen(yuri[j]) < strlen(yuri[j+1]))
    
68.             {
    
69.                 strcpy(ttemp,yuri[j]);
    
70.                 strcpy(yuri[j],yuri[j+1]);
    
71.                 strcpy(yuri[j+1],ttemp);
    
72. 
    
73.             }
    
74.         }
    
75.     }
    
76.     return yuri[0];
    
77. }

复制代码

一直过不了这道题 。求解。。。

最佳答案

月排行榜 / 总排行榜

Qmh

2019-11-1 23:29:02

这道题可以用DP做，状态转移方程是f[i][j]=max(f[i-1][j],f[i][j-1])
如果两个字符相等，加上f[i][j]=max(f[i][j],f[i-1][j-1]+1)
条件是a[i-1]==b[j-1]
思想是将这个问题分成许多子结构，并求出最优的子结构，再根据子结构的答案，算出整体答案
代码如下↓↓↓

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.         char a[105],b[105];
   
6.         int n=1,m=1;
   
7.         while ((a[n]=getchar())!='\n') n++;
   
8.         while ((b[m]=getchar())!='\n') m++;
   
9.         n--;m--;
   
10.         int f[n+1][m+1];
    
11.         memset(f,0,sizeof(f));
    
12.         char c[105];
    
13.         int k=1;
    
14.         for (int i=1;i<=n;i++)
    
15.         {
    
16.                 for (int j=1;j<=m;j++)
    
17.                 {
    
18.                         f[i][j]=max(f[i-1][j],f[i][j-1]);
    
19.                         if (a[i-1]==b[j-1])
    
20.                         {
    
21.                                 f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    
22.                                 if (f[i][j]==f[i-1][j-1]+1)
    
23.                                 {
    
24.                                         c[k]=a[i];
    
25.                                         k++;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.         }
    
30.         for (int i=1;i<k;i++)
    
31.         {
    
32.                 printf("%c",c[i]);
    
33.         }
    
34.        
    
35.         return 0;
    
36. }

复制代码

希望对楼主有帮助
（本人学生党，发帖不易，望众大佬勿喷）

跳转到最佳答案楼层

bin554385863

1. #include <stdio.h>
   
2. void func(char * str1, char * str2)
   
3. {
   
4.         for (char * i = str1; *i != '\0'; i++)
   
5.         {
   
6.                 for (char * j = str2; *j != '\0'; j++)
   
7.                 {
   
8.                         if (*i == *j)
   
9.                         {
   
10.                                 printf("%c", *j);
    
11.                         }
    
12.                 }
    
13.         }
    
14. }
    
15. int main(int argc, char * argv[])
    
16. {
    
17.         char str1[] = "cnblog";
    
18.         char str2[] = "belong";
    
19.         func(str1, str2);
    
20.         return 0;
    
21. }

复制代码

-------------------------------------------------------------------------------------------
正在运行:"E:\Program Files (x86)\QS源代码\Console - KNENE.exe"

nblog
进程退出返回值 0 (0x0)   运行时间 : 0.047 秒
按任意键继续...

Croper

动态规划思路

对于两字符串A，B，若其长度为a，b，那么其最长公共子串一定是下面4种构成方式中最长的

1、A.substr(0,a-1)和B的最长公共子串
2、A.和B.sub(0,b-1)的最长公共子串
3.若A.back()与B[n]拥有相同的字符c,那么A.substr(0,a-1)与B.substr(0.n-1)的最长公共子串加上c后仍然是A与B的公共子串，若有多个相同，那么n尽量大时，此方法构造成的子串最长；
4.在情况3中，调换A和B的位置

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #define max(a,b)    (((a) > (b)) ? (a) : (b))
   
5. #define min(a,b)    (((a) < (b)) ? (a) : (b))
   
6. 
   
7. using namespace std;
   
8. 
   
9. string longestCommonSubstr(string s1, string s2) {
   
10.         vector<vector<string>> dp(s1.size(), vector<string>(s2.size()));
    
11.         int maxi = (int)s1.size() + (int)s2.size() - 1;
    
12.         for (int i = 0; i < maxi; ++i) {
    
13.                 int maxj = min(min(i + 1, maxi - i), (int)max(s1.size(), s2.size()));
    
14.                 for (int j = 0; j < maxj; ++j) {
    
15.                         int a = min(i, (int)s1.size() - 1) - j;
    
16.                         int b = max(0, i - (int)s2.size() + 1) + j;
    
17. 
    
18.                         string sub1, sub2, sub3, sub4;
    
19.                         if (a > 0) {
    
20.                                 sub1 = dp[a - 1][b];
    
21.                         }
    
22.                         if (b > 0) {
    
23.                                 sub2 = dp[a][b - 1];
    
24.                         }
    
25.                         for (int k = b; k >= 0; --k) {
    
26.                                 if (s1[a] == s2[k]) {
    
27.                                         if (a != 0 && k != 0) {
    
28.                                                 sub3 = dp[a - 1][k - 1];
    
29.                                         }
    
30.                                         sub3.push_back(s1[a]);
    
31.                                         break;
    
32.                                 }
    
33.                         }
    
34. 
    
35.                         for (int k = a; k >= 0; --k) {
    
36.                                 if (s1[k] == s2[b]) {
    
37.                                         if (k != 0 && b != 0) {
    
38.                                                 sub4 = dp[k - 1][b - 1];
    
39.                                         }
    
40.                                         sub4.push_back(s2[b]);
    
41.                                         break;
    
42.                                 }
    
43.                         }
    
44.                         if (dp[a][b].size() < sub1.size()) dp[a][b] = sub1;
    
45.                         if (dp[a][b].size() < sub2.size()) dp[a][b] = sub2;
    
46.                         if (dp[a][b].size() < sub3.size()) dp[a][b] = sub3;
    
47.                         if (dp[a][b].size() < sub4.size()) dp[a][b] = sub4;
    
48.                 }
    
49.         }
    
50.         return dp[s1.size() - 1][s2.size() - 1];
    
51. }
    
52. 
    
53. int main() {
    
54.         cout << longestCommonSubstr("cnblog", "belong");
    
55.         system("pause");
    
56. }

复制代码

AmosAlbert

DP

Qmh

这道题可以用DP做，状态转移方程是f[i][j]=max(f[i-1][j],f[i][j-1])
如果两个字符相等，加上f[i][j]=max(f[i][j],f[i-1][j-1]+1)
条件是a[i-1]==b[j-1]
思想是将这个问题分成许多子结构，并求出最优的子结构，再根据子结构的答案，算出整体答案
代码如下↓↓↓

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.         char a[105],b[105];
   
6.         int n=1,m=1;
   
7.         while ((a[n]=getchar())!='\n') n++;
   
8.         while ((b[m]=getchar())!='\n') m++;
   
9.         n--;m--;
   
10.         int f[n+1][m+1];
    
11.         memset(f,0,sizeof(f));
    
12.         char c[105];
    
13.         int k=1;
    
14.         for (int i=1;i<=n;i++)
    
15.         {
    
16.                 for (int j=1;j<=m;j++)
    
17.                 {
    
18.                         f[i][j]=max(f[i-1][j],f[i][j-1]);
    
19.                         if (a[i-1]==b[j-1])
    
20.                         {
    
21.                                 f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    
22.                                 if (f[i][j]==f[i-1][j-1]+1)
    
23.                                 {
    
24.                                         c[k]=a[i];
    
25.                                         k++;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.         }
    
30.         for (int i=1;i<k;i++)
    
31.         {
    
32.                 printf("%c",c[i]);
    
33.         }
    
34.        
    
35.         return 0;
    
36. }

复制代码

希望对楼主有帮助
（本人学生党，发帖不易，望众大佬勿喷）