当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-01-27   作者:bylijinnan   来源:转载   浏览:
摘要: public class MaxCatenate { /* * Q.37 有n 个长为m+1 的字符串,如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符串可以联接, * 问这n 个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。 */ public static void main(String[] args){
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;
    }
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
有n 个长为m+1 的字符串, 如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符
有n 个长为m+1 的字符串,如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
按要求分解字符串,输入两个数M,N,M代表输入的M串字符串,N代表输出的每串字符串的位数,不够补0
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
今天一网友求解一问题:截取下图的字符串: 这个不很简单么,截取字符串函数substring(字符串,起始
一、查找文件   使用快捷键【ctrl+shift+R】弹出弹出文件查找框,如下图所示:    二、查找包含
需求如下: 整个目录下大概有40几M,文件无数,由于时间久了, 记不清那个字符串具体在哪个文件,于
今天一网友求解一问题:截取下图的字符串: 这个不很简单么,截取字符串函数substring(字符串,起始
概述 字符串T = abcabaabaadac, 字符串P = abaa,判断P是否是T的子串,就是字符串匹配问题了,T叫做
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号