算法习题37：有n个长为m+1的字符串， 如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接 - ylf13的专栏 - 博客频道 - CSDN.NET

算法习题37：有n个长为m+1的字符串， 如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接 - ylf13的专栏 - 博客频道 - CSDN.NET
有n个长为m+1的字符串，
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，
问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
http://bylijinnan.iteye.com/blog/1377768

1. 
   
2.     public  void maxCatenate(String[] text){  
3.         int size=text.length;  
4.         int[][] adjMatrix=new int[size][size];  
5.         //create Graph.Use adjacent matrix  
6.         for(int i=0;i<size;i++){  
7.             for(int j=0;j<size;j++){  
8.                 if(this.hasEdge(text[i],text[j])){  
9.                     adjMatrix[i][j]=1;  
10.                 }  
11.             }  
12.         }  
13.         //create a new array to keep the 'adjMatrix'unchanged.  
14.         int[][] finalCost=new int[size][size];  
15.         for(int i=0;i<size;i++){  
16.             for(int j=0;j<size;j++){  
17.                 finalCost[i][j]=adjMatrix[i][j];  
18.             }  
19.         }  
20.         int max=0;  
21.         for(int k=0;k<size;k++){  
22.             for(int i=0;i<size;i++){  
23.                 for(int j=0;j<size;j++){  
24.                     if(finalCost[i][k]!=0&&finalCost[k][j]!=0&&  
25.                             finalCost[i][k]+finalCost[k][j]>finalCost[i][j]  ){  
26.                         finalCost[i][j]=finalCost[i][k]+finalCost[k][j];  
27.                         max=(max>finalCost[i][j]?max:finalCost[i][j]);  
28.                     }  
29.                 }  
30.             }  
31.         }  
32.           
33.         for(int i=0;i<size;i++){  
34.             if(finalCost[i][i]>1){//not '>0',consider "bbbb"  
35.                 System.out.println("circle detected");  
36.                 return;  
37.             }  
38.         }  
39.         System.out.println("maxLength is "+(max+1));  
40.     }  
41.       
42.     //true if strA's last m characters equals to strB's first m characters  
43.     public boolean hasEdge(String strA,String strB){  
44.         boolean result=false;  
45.         String suffix=strA.substring(1);  
46.         result=strB.startsWith(suffix);  
47.         return result;  
48.     }  

Read full article from 算法习题37：有n个长为m+1的字符串， 如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接 - ylf13的专栏 - 博客频道 - CSDN.NET