HDU 1503 带回朔路径的最长公共子串

http://acm.hdu.edu.cn/showproblem.php?pid=1503

这道题又WA了好几次

在裸最长公共子串基础上加了回溯功能，就是给三种状态各做一个

不同的标记。dp[n][m]开始回找，找到这条最长串的组成。

WA点有几个都被我遇到了

一个是最长公共串为0时，两个串直接输出

一个是最长公共串为1时，后续串的处理

这里要记得是dp回溯的方式

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<stack>

#include<cstring>

using namespace std;

struct donser

{

    int x,y;

};

int main()

{

    string s,t;

    while(cin>>s>>t)

    {

        int i,j,m=,n=,a1,b1,a2,b2;

        stack<donser> sta;

        struct donser dong;

        struct donser dongs;

        int dp[][],lable[][];

        n=s.length();

        m=t.length();

        for(i=;i<n;i++)

        {

            for(j=;j<m;j++)

            {

                if(s[i]==t[j])

                {

                    dp[i+][j+]=dp[i][j]+;

                    lable[i+][j+]=;

                }

                else

                {

                    if(dp[i][j+]>dp[i+][j])

                    {

                        dp[i+][j+]=dp[i][j+];

                        lable[i+][j+]=;

                    }

                    else

                    {

                        dp[i+][j+]=dp[i+][j];

                        lable[i+][j+]=;

                    }

                }

            }

        }

        i=n;j=m;a1=a2=n;b1=b2=m;

        if(dp[n][m]==){cout<<s<<t<<endl;}

        else{

        while(lable[i][j]!=)

        {

            if(lable[i][j]==)

            {

                i--;j--;

                dong.x=i;

                dong.y=j;

                sta.push(dong);

            }

            else if(lable[i][j]==)

            {

                i--;

            }

            else if(lable[i][j]==)

            {

                j--;

            }

        }

        if(sta.empty()!=)

        {

            dong=sta.top();

            sta.pop();

            a1=dong.x;

            b1=dong.y;

            for(i=;i<a1;i++)

            {

                cout<<s[i];

            }

            for(i=;i<b1;i++)

            {

                cout<<t[i];

            }

        }

        if(sta.empty()==)

        {

            for(i=a1;i<n;i++)

            {

                cout<<s[i];

            }

            for(i=b1+;i<m;i++)

            {

                cout<<t[i];

            }

        }

        while(sta.empty()!=)

        {

            a1=dong.x;

            b1=dong.y;

            dongs=sta.top();

            sta.pop();

            a2=dongs.x;

            b2=dongs.y;

            for(i=a1;i<a2;i++)

            {

                cout<<s[i];

            }

            for(j=b1+;j<b2;j++)

            {

                cout<<t[j];

            }

            dong=dongs;

        }

        for(i=a2;i<n;i++)

        {

            cout<<s[i];

        }

        for(i=b2+;i<m;i++)

        {

            cout<<t[i];

        }

        cout<<endl;}

    }

    return ;

}

巴特西

HDU 1503 带回朔路径的最长公共子串

最新文章

热门文章