【100题】第三十七 字符串连接问题

一，题目：

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

二，分析：
将各个字符串作为一个节点，首尾链接就好比是一条边，将两个节点连接起来，于是问题就变成一个有关图的路径长度的问题。链接所得的字符串最长长度即为从图的某个节点出发所能得到的最长路径问题，与最短路径类似，可以应用弗洛伊德算法求解。对于循环，即可认为各个节点通过其他节点又回到自己，反应在路径长度上，就表示某个节点到自己节点的路径大于零（注：初始化个节点到自己的长度为零）。

三，源码

public class MaxCatenate {

	public static void main(String[] args) 
	{
		String[] text = new String[]{
				 "abcd",
				  "bcde",
				   "cdea",
					"deab",
					 "eaba",
					  "abab",
					"deac",
				   "cdei",
				  "bcdf",
				   "cdfi",
				    "dfic",
				   "cdfk",
				  "bcdg",
		};
		maxCatenate(text);
	}
	
	public static void maxCatenate(String[] text)
	{
		int[][] G = new int[text.length][text.length];
		for(int i=0; i<G.length; i++)
		{
			String suffix = text[i].substring(1);
			for(int j=0; j<G.length; j++)
				if(text[j].indexOf(suffix)==0)
					G[i][j] = 1;
		}
		for(int k=0; k<G.length; k++)
			for(int i=0; i<G.length; i++)
				for(int j=0; j<G.length; j++)
					if(G[i][k]!=0&&G[k][j]!=0)
					{
						int dist = G[i][k] + G[k][j];
						if(dist>G[i][j])
						{
							G[i][j] = dist;
						}
					}
		for(int i=0; i<G.length; i++)
			if(G[i][i]>1)
			{
				System.out.println("circle is deteted!");
				return;
			}
		int max = 0;
		for(int i=0; i<G.length; i++)
			for(int j=0; j<G.length; j++)
				max = Math.max(max, G[i][j]);
		System.out.println("Max length is " + (max+text[0].length()));
	}

}