本文主要是介绍【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()));}}
这篇关于【100题】第三十七 字符串连接问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
