字符串联接 【微软面试100题 第三十七题】

题目要求：

　　有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接。

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

题目分析：

　　1.每个字符串都是长为m+1的字符串，两个字符串匹配后长度应该为1+m+1=m+2;

　 2.用图的思想来解。如果某两个顶点匹配，则在图中的该两点连线，当遍历完所有点之后，判断该图是否有环，没有就求该图的最长路径；

　 3.求图的最长路径与求最短路径类似，可以参考Floyd最短路径算法；

代码实现：

代码链接：http://blog.csdn.net/cxh342968816/article/details/6637006

#include<iostream>
#include<string>
using namespace std;

#define length 14

bool Isconnect(string str1,string str2)
{
    if(str1.size()!=str2.size())
        return false;
    int m=str1.size();
    for(int i=0;i<m-1;i++)
    {
        if(str1[i+1]!=str2[i])
            return false;
    }
    return true;
}

void Maxstring(string str[])
{
    int G[length][length]={0};
    for(int i=0;i<length;i++)
        for(int j=0;j<length;j++)
            if(Isconnect(str[i],str[j]))
                G[i][j]=1;
    for(int i=0;i<length;i++)
    {
        for(int j=0;j<length;j++)
        {
            for(int k=0;k<length;k++)
            {
                if(G[i][k]!=0&&G[k][j]!=0)
                {
                    int dis=G[i][k]+G[k][j];
                    if(dis>G[i][j])
                        G[i][j]=dis;
                }

            }
        }
    }
    for(int i=0;i<length;i++)
    {
        if(G[i][i]>1)
        {
            cout<<"circle is deteted"<<endl;
            return;
        }
    }
    int max=0;
    for(int i=0;i<length;i++)
    {
        for(int j=0;j<length;j++)
        {
            if(G[i][j]>max)
                max=G[i][j];

        }
    }
    cout<<"Max length is "<<max+str[0].size()<<endl;

}



int main()
{
    string str[length]={
        "abcd",
        "bcde",
        "cdea",
        "deab",
        "eaba",
        "abab",
        "deac",
        "cdei",
        "bcdf",
        "cdfi",
        "dfic",
        "cdfk",
        "bcdg",
//        "babc"};//用这个替换下面一行，就会形成环
        "babf"};
        Maxstring(str);

}