【编程题目】有 n 个长为 m+1 的字符串，如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配...

时间：2022-08-13 16:01:55

37.（字符串）
有 n 个长为 m+1 的字符串，
如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配，则两个字符串可以联接，
问这 n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

分析：如果出现循环，则返回错误 这句不懂 我采用了绝对不会产生环的方法来做。

具体做法是先给每个字符串建一个vector 存入每个字符串后面可以匹配的字符串序号

然后遍历所有的搭配情况，找到最长的。

我的遍历代码很丑... 可谓又臭又长..... 深深的自我鄙视。

/*

37.（字符串）

有 n 个长为 m+1 的字符串，

如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配，则两个字符串可以联接，

问这 n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

start time = 18:27

end time =

*/

#include <iostream>

#include <vector>

#include <string>

using namespace std;

//判断两个字符串能否拼接 0表示不能 2表示s1在前 1表示s2在前

int contact(string s1, string s2, int m)

{

    if(s1.substr(, m) == s2.substr(s2.length() - m, m))

        return ;

    else if(s2.substr(, m) == s1.substr(s1.length() - m, m))

        return ;

    else

        return ;

}

void getMax0(vector<int> now, vector<vector<int>> can_compare, vector<int> &max)

{

    bool isfind = false;

    int last = now.back();

    vector<int>::iterator it;

    for(it = can_compare.at(last).begin(); it < can_compare.at(last).end(); it++)

    {

        bool isHave = false;

        vector<int>::iterator it2;

        for(it2 = now.begin(); it2 < now.end(); it2++)

        {

            if((*it) == (*it2))

            {

                isHave = true;

                break;

            }

        }

        if(isHave == false)

        {

            isfind = true;

            now.push_back(*it);

            getMax0(now, can_compare, max);

            now.pop_back();

        }

    }

    if(isfind == false)

    {

        if(now.size() > max.size())

        {

            max = now;

        }

    }

}

vector<int> getMax(vector<vector<int>> can_compare)

{

    vector<int> contact;

    vector<int> max;

    vector<int> now;

    vector<vector<int>>::iterator it;

    for(int i = ; i < can_compare.size(); i++)

    {

        now.push_back(i);

        getMax0(now, can_compare, max);

        now.clear();

    }

    return max;

}

//返回可能的最大长度

string maxLength(vector<string> S, int m)

{

    //找到每个字符串在前时有哪些其他字符串可以与其匹配

    vector<vector<int>> can_compare;

    vector<string>::iterator it;

    for(it = S.begin(); it < S.end(); it++)

    {

        vector<int> can_member;

        vector<string>::iterator it2;

        int n = ;

        for(it2 = S.begin(); it2 < S.end(); it2++)

        {

            if(it != it2)

            {

                if(contact(*it, *it2, m) == )

                {

                    can_member.push_back(n);

                }

            }

            n++;

        }

        can_compare.push_back(can_member);

    }

    vector<int> maxStringMember = getMax(can_compare);

    vector<int>::iterator it3;

    string ans = S.at(maxStringMember.at());

    for(it3 = maxStringMember.begin() + ; it3 < maxStringMember.end(); it3++)

    {

        string after = S.at(*it3);

        ans.append(after.substr(after.length() - , ));

    }

    cout << "the max length is "<< ans.length() << endl;

    cout << "the string is " << ans << endl;

    return ans;

}

int main()

{

    vector<string> S;

    string s1 = "abd";

    S.push_back(s1);

    string s2 = "bcd";

    S.push_back(s2);

    string s3 = "cde";

    S.push_back(s3);

    string s4 = "def";

    S.push_back(s4);

    string ans = maxLength(S, );

    return ;

}

在网上看答案，发现这是一道图的题。可以通过floyd求最大路径来解决。

从网上找了一份代码，验证了可以使用。

代码中D[v][w] 是顶点v到顶点w的最大路径

p[v][w][u]是顶点v到顶点w最大路径上第u个顶点的序号。

INFINITY 顶点间无边时的值，是个负数

算法原理是，如果发现v 、w顶点中插入顶点u距离变大，则更新最大路径和最大距离。

代码如下：http://blog.csdn.net/cxllyg/article/details/7606599

#include <iostream>

#include <string>

using namespace std;

#define INFINITY -10000

#define MAX_VERTEX_NUM 20 

typedef struct MGraph{

    string vexs[MAX_VERTEX_NUM];//顶点信息，这里就是要处理的字符串，每个字符串看做一个顶点

    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵，符合条件的两个字符串之间有边

    int vexnum, arcnum;//顶点数就是字符串的个数

}MGraph;

void CreateDG(MGraph &G)//构造有向图

{

    int i, j;

    int m;

    cout<<"请输入要处理的字符串个数：";

    cin>>G.vexnum;

    cout<<"请输入这"<<G.vexnum<<"个字符串：";

    for(i=; i<G.vexnum; i++)

        cin>>G.vexs[i];

    cout<<"请输入m：";

    cin>>m;

    for(i=; i<G.vexnum; i++)

        for(j=; j<G.vexnum; j++)

        {

            if(G.vexs[i].substr(G.vexs[i].size()-m,m)==G.vexs[j].substr(,m))//根据前后m个字符是否匹配确定两字符串之间是否有边

                G.arcs[i][j]=;

            else

                G.arcs[i][j]=INFINITY;

        }

}

//利用弗洛伊德算法求各顶点间的最长路径，p保存路径，D保存各顶点间的最长路径，如果出现循环，函数返回false，反之返回true

bool Largeset_FLOYD(MGraph G, int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM], int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM])

{

    int v, w, u;

    int i, j;

    for(v=; v<G.vexnum; v++)

        for(w=; w<G.vexnum; w++)

        {

            D[v][w]=G.arcs[v][w];

            for(u=; u<G.vexnum; u++)

                p[v][w][u]=-;

            if(D[v][w]>INFINITY)

            {

                p[v][w][]=v;

                p[v][w][]=w;

            }

        }

    for(u=; u<G.vexnum; u++)

        for(v=; v<G.vexnum; v++)

            for(w=; w<G.vexnum; w++)

            {

                if(D[v][u]>INFINITY && D[u][w]>INFINITY && D[v][u]+D[u][w]>D[v][w] )//改进的弗洛伊德算法，求最长路径

                {

                    D[v][w]=D[v][u]+D[u][w];

                    //更新p，以便打印路径

                    for(i=; i<G.vexnum; i++)

                    {

                        if(p[v][u][i]!=-)

                            p[v][w][i]=p[v][u][i];

                        else

                            break;

                    }

                    for(j=; j<G.vexnum; j++)

                    {

                        if(p[u][w][j]!=-)

                            p[v][w][i++]=p[u][w][j];

                        else

                            break;

                    }

                }

            }

    //判断是否有循环

    for(v=; v<G.vexnum; v++)

        if(D[v][v]!=INFINITY)

                return false;

    return true;

}

void main()

{

    int i, j;

    int posx, posy;

    MGraph g;

    CreateDG(g);

    int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];

    int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

    bool flag=true;

    flag=Largeset_FLOYD(g, p, D);

/*    for(i=0; i<g.vexnum; i++)

    {

        for(j=0; j<g.vexnum; j++)

            cout<<D[i][j]<<" ";

        cout<<endl;

    }*/

    if(flag)

    {

        cout<<"最大长度为：";

        int max=-;

        for(i=; i<g.vexnum; i++)

            for(j=; j<g.vexnum; j++)

            {

                if(D[i][j]>max)

                {

                    max=D[i][j];

                    posx=i;

                    posy=j;

                }

            }

        cout<<max<<endl;

        cout<<"字符串链为：";

        for(i=; i<g.vexnum; i++)//打印字符串链

        {

            if(p[posx][posy][i]!=-)

                cout<<g.vexs[p[posx][posy][i]]<<" ";

        }

        cout<<endl;

    }

    else

        cout<<"错误：出现循环"<<endl;

    system("pause");

}

相关文章