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

public class MaxCatenate {  
  
	/*
	 * Q.37 有n 个长为m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接，
	 * 问这n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
	 */
    public static void main(String[] args){  
        String[] text = new String[]{  
                 "abcd",  
                  "bcde",  
                   "cdea",  
                    "deab",  
                     "eaba",  
                      "abab",  
                      //"babc", 
                    "deac",  
                   "cdei",  
                  "bcdf",  
                   "cdfi",  
                    "dfic",  
                   "cdfk",  
                  "bcdg",  
        };  
        new MaxCatenate().maxCatenate(text);  
    } 
    
    public  void maxCatenate(String[] text){
    	int size=text.length;
    	int[][] adjMatrix=new int[size][size];
    	//create Graph.Use adjacent matrix
    	for(int i=0;i<size;i++){
    		for(int j=0;j<size;j++){
    			if(this.hasEdge(text[i],text[j])){
    				adjMatrix[i][j]=1;
    			}
    		}
    	}
    	//create a new array to keep the 'adjMatrix'unchanged.
    	int[][] finalCost=new int[size][size];
    	for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				finalCost[i][j]=adjMatrix[i][j];
			}
		}
    	int max=0;
    	for(int k=0;k<size;k++){
    		for(int i=0;i<size;i++){
    			for(int j=0;j<size;j++){
    				if(finalCost[i][k]!=0&&finalCost[k][j]!=0&&
    						finalCost[i][k]+finalCost[k][j]>finalCost[i][j]	){
    					finalCost[i][j]=finalCost[i][k]+finalCost[k][j];
    					max=(max>finalCost[i][j]?max:finalCost[i][j]);
    				}
    			}
    		}
    	}
    	
    	for(int i=0;i<size;i++){
    		if(finalCost[i][i]>1){//not '>0',consider "bbbb"
    			System.out.println("circle detected");
    			return;
    		}
    	}
    	System.out.println("maxLength is "+(max+1));
    }
    
    //true if strA's last m characters equals to strB's first m characters
    public boolean hasEdge(String strA,String strB){
    	boolean result=false;
    	String suffix=strA.substring(1);
    	result=strB.startsWith(suffix);
    	return result;
    }
}