数据结构：LCS最长公共子串动态规划DP + DFS深度优先遍历

朱雀 2022-05-31 12:24 190阅读 0赞

# 问题是什么 #

这道题和上一道题不一样的地方就是寻找最长的子串，而不是子序列，这是一个典型的动态规划DP问题

# 代码如下 #

string a="qwertyuiopasdfghjkl";
    string b="afdstyuio555pasdf7y5i5h8";
    int lena=a.length();
    int lenb=b.length();
    
    int lcs(int i,int j)
    {
        if(i==lena || j==lenb)
            return 0;
        if(a[i]==b[j])
        {
            cout<<a[i];
            return 1+lcs(i+1,j+1);
        }
        else
            if(i<j)
                return lcs(i+1,j);
            else
                return lcs(i,j+1);
    }
    
    void LCS(string a,string b)
    {
        int lena=a.length();
        int lenb=b.length();
        int **cal=new int*[lena+1];
        for(int i=0;i<=lena;i++)
            cal[i]=new int[lenb+1];
    
        for(int i=0;i<=lena;i++)
            for(int j=0;j<=lenb;j++)
                cal[i][j]=0;
    
        int max=0;
        int x,y;
        for(int i=1;i<=lena;i++)
        {
            for(int j=1;j<=lenb;j++)
            {
                if (a[i-1]==b[j-1])
                    cal[i][j]=cal[i-1][j-1]+1;
                else
                    cal[i][j]=0;
    
                if(cal[i][j]>max)
                {
                    max=cal[i][j];
                    x=i;
                    y=j;
                }
            }
        }
        int c=max;
        char res[1000];
        res[c--]='\0';
        int i=x-1,j=y-1;
        while (i>=0 &&j>=0)
        {
            if(a[i]==b[j])
            {
                res[c--]=a[i];
                i--;
                j--;
            }
            else
                break;
    
        }
        cout<<max<<endl;
        cout<<res<<endl;
    
        for(int i=0;i<=lena;i++)
             delete [] cal[i];
        delete [] cal;
    
    }
    int main()
    {
    
        LCS(a,b);
        cout<<endl;
        cout<<lcs(0,0);
        system("pause");
    }