学步园

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

将各个字符串作为一个节点，首尾链接就好比是一条边，将两个节点连接起来，
于是问题就变成一个有关图的路径长度的问题。

链接所得的字符串最长长度即为从图的某个节点出发所能得到的最长路径问题，
与最短路径类似，可以应用弗洛伊德算法求解。
对于循环，即可认为各个节点通过其他节点又回到自己，反应在路径长度上，
就表示某个节点到自己节点的路径大于零
*/

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;

#define N 14

//判断两个字符是否连接 
bool isCon(string str1,string str2)
{
	if(str1.size()!=str2.size())
		return false;
	int m=str1.size();
	//str1的后m个 与 str2的前m个是否相同 
	for(int i=0;i<m-1;i++)
		if(str1[i+1]!=str2[i])
			return false;
	return true;
}

void maxString(string str[],int n)
{
	int m[N][N],dis,i,j,k,max;
	
	memset(m,0,sizeof(m));
	
	//先绘图，可以相邻为1 
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(isCon(str[i],str[j]))
					m[i][j]=1;
					
	// floy算法  最长的路径 
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			for(k=0;k<n;k++)
			{
				if(m[i][k]!=0&&m[k][j]!=0)
				{
					dis=m[i][k]+m[k][j];
					if(dis>m[i][j])
						m[i][j]=dis;
				}
			}	
			
	//有环路 
	for(i=0;i<n;i++)
		if(m[i][i]>1)
		{
			cout<<"circle is deteted"<<endl;
			return ;
		}
	
	// 找最大值 
	max=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(m[i][j]>max)
				max=m[i][j];
	cout<<"Max length is "<<max+str[0].size()<<endl;
}

int main()
{
	string str[]={
		"abcd",
		"bcde",
		"cdea",
		"deab",
		"eaba",
		"abab",
		"deac",
		"cdei",
		"bcdf",
		"cdfi",
		"dfic",
		"cdfk",
		"bcdg",
		"babc"};
	maxString(str,14);//环 
	
	string str2[]={
		"abd",
		"bcd",
		"def",
		"cde"};
	maxString(str2,4);//bcdef 5
	
	string str3[]={
		"abcd",
		"qwer",
		"bcde",
		"wert",
		"erty",
		"cdeh",
		"tuyi",
		"rtyu"};
	maxString(str3,8);//qwertyu 7
	return 0;
}