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

ksdeer

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

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

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

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

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

样例输入
cnblogs

belong

样例输出
blog

#include <stdio.h>
#include <string.h>
int k = 0;
char yuri[101][101];

char *str(char *fuck,char *shit,char *temp);
int main(void)
{
    char fuck[101];
    char shit[101];
    while(scanf("%s\n%s", fuck,shit) != EOF)
    {
        char temp[101];
        if(strlen(fuck) > strlen(shit))
        {
            printf("%s\n", str(fuck,shit,temp));
        }
        else
        {
            printf("%s\n", str(shit,fuck,temp));
        }
        for(int i = 0; i < 101; i++)
        {
            for(int j = 0; j < 101; j++)
            {
                yuri[i][j] = '\0';
            }
        }
    }
    return 0;
}
char *str(char *fuck,char *shit, char *temp)
{
    int w = 0;
    int k = 0;
    int fault = 0;
    for(int u = 0; u < strlen(shit); u++)
    {
        for(int i = u; i < strlen(shit); i++)
        {
            for(int j = w; j < strlen(fuck); j++)
            {
                if(shit[i] == fuck[j])
                {
                    temp[k] = shit[i];
                    k++;
                    w = j + 1;
                    break;
                }
            }
        }
        temp[k] = '\0';
        strcpy(yuri[fault],temp);
        fault++;
        for(int i = 0; i < k; i++)
        {
            temp[i] = '\0';
        }
        k = 0;
        w = 0;
    }
    char ttemp[101];
    for(int i = 0; i < fault - 1; i++)
    {
        for(int j = 0; j < fault - 2; j++)
        {
            if(strlen(yuri[j]) < strlen(yuri[j+1]))
            {
                strcpy(ttemp,yuri[j]);
                strcpy(yuri[j],yuri[j+1]);
                strcpy(yuri[j+1],ttemp);

            }
        }
    }
    return yuri[0];
}

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

最佳答案

月排行榜 / 总排行榜

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]
思想是将这个问题分成许多子结构，并求出最优的子结构，再根据子结构的答案，算出整体答案
代码如下↓↓↓

#include <bits/stdc++.h>
using namespace std;
int main()
{
        char a[105],b[105];
        int n=1,m=1;
        while ((a[n]=getchar())!='\n') n++;
        while ((b[m]=getchar())!='\n') m++;
        n--;m--;
        int f[n+1][m+1];
        memset(f,0,sizeof(f));
        char c[105];
        int k=1;
        for (int i=1;i<=n;i++)
        {
                for (int j=1;j<=m;j++)
                {
                        f[i][j]=max(f[i-1][j],f[i][j-1]);
                        if (a[i-1]==b[j-1])
                        {
                                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
                                if (f[i][j]==f[i-1][j-1]+1) 
                                {
                                        c[k]=a[i];
                                        k++;
                                }
                        }
                }
        }
        for (int i=1;i<k;i++)
        {
                printf("%c",c[i]);
        }
        
        return 0;
}

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

跳转到最佳答案楼层

bin554385863

#include <stdio.h>
void func(char * str1, char * str2)
{
        for (char * i = str1; *i != '\0'; i++)
        {
                for (char * j = str2; *j != '\0'; j++)
                {
                        if (*i == *j)
                        {
                                printf("%c", *j);
                        }
                }
        }
}
int main(int argc, char * argv[])
{
        char str1[] = "cnblog";
        char str2[] = "belong";
        func(str1, str2);
        return 0;
}

-------------------------------------------------------------------------------------------
正在运行:"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的位置

#include <iostream>
#include <vector>
#include <string>
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define min(a,b)    (((a) < (b)) ? (a) : (b))

using namespace std;

string longestCommonSubstr(string s1, string s2) {
        vector<vector<string>> dp(s1.size(), vector<string>(s2.size()));
        int maxi = (int)s1.size() + (int)s2.size() - 1;
        for (int i = 0; i < maxi; ++i) {
                int maxj = min(min(i + 1, maxi - i), (int)max(s1.size(), s2.size()));
                for (int j = 0; j < maxj; ++j) {
                        int a = min(i, (int)s1.size() - 1) - j;
                        int b = max(0, i - (int)s2.size() + 1) + j;

                        string sub1, sub2, sub3, sub4;
                        if (a > 0) {
                                sub1 = dp[a - 1][b];
                        }
                        if (b > 0) {
                                sub2 = dp[a][b - 1];
                        }
                        for (int k = b; k >= 0; --k) {
                                if (s1[a] == s2[k]) {
                                        if (a != 0 && k != 0) {
                                                sub3 = dp[a - 1][k - 1];
                                        }
                                        sub3.push_back(s1[a]);
                                        break;
                                }
                        }

                        for (int k = a; k >= 0; --k) {
                                if (s1[k] == s2[b]) {
                                        if (k != 0 && b != 0) {
                                                sub4 = dp[k - 1][b - 1];
                                        }
                                        sub4.push_back(s2[b]);
                                        break;
                                }
                        }
                        if (dp[a][b].size() < sub1.size()) dp[a][b] = sub1;
                        if (dp[a][b].size() < sub2.size()) dp[a][b] = sub2;
                        if (dp[a][b].size() < sub3.size()) dp[a][b] = sub3;
                        if (dp[a][b].size() < sub4.size()) dp[a][b] = sub4;
                }
        }
        return dp[s1.size() - 1][s2.size() - 1];
}

int main() {
        cout << longestCommonSubstr("cnblog", "belong");
        system("pause");
}

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]
思想是将这个问题分成许多子结构，并求出最优的子结构，再根据子结构的答案，算出整体答案
代码如下↓↓↓

#include <bits/stdc++.h>
using namespace std;
int main()
{
        char a[105],b[105];
        int n=1,m=1;
        while ((a[n]=getchar())!='\n') n++;
        while ((b[m]=getchar())!='\n') m++;
        n--;m--;
        int f[n+1][m+1];
        memset(f,0,sizeof(f));
        char c[105];
        int k=1;
        for (int i=1;i<=n;i++)
        {
                for (int j=1;j<=m;j++)
                {
                        f[i][j]=max(f[i-1][j],f[i][j-1]);
                        if (a[i-1]==b[j-1])
                        {
                                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
                                if (f[i][j]==f[i-1][j-1]+1) 
                                {
                                        c[k]=a[i];
                                        k++;
                                }
                        }
                }
        }
        for (int i=1;i<k;i++)
        {
                printf("%c",c[i]);
        }
        
        return 0;
}

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