有n 个长为m+1 的字符串，求前后m个字符匹配所能形成的最长字符串链

  1 package strings;
  2 
  3 /**
  4  * @author ycsun E-mail:stevesun521@gmail.com
  5  * @version 创建时间：2012-10-2 下午8:36:17 类说明
  6  */
  7 public class MaxCatenate {
  8 
  9     /*
 10      * 有n 个长为m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接， 问这n
 11      * 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
 12      */
 13     private int m = 1;
 14     private int[][] adjMatrix;
 15     private int vertexnum = 0;
 16     private String[] text;
 17     private int[][] d;
 18     private int[][] path;
 19     private int maxPosX, maxPosY;
 20     private int maxLenth = Integer.MIN_VALUE;
 21 
 22     public MaxCatenate(int m, String[] text) {
 23         this.m = m;
 24         this.vertexnum = text.length;
 25         this.adjMatrix = new int[vertexnum][vertexnum];
 26         this.d = new int[vertexnum][vertexnum];
 27         this.text = text;
 28         this.path = new int[vertexnum][vertexnum];
 29     }
 30 
 31     public boolean hasEdge(String strA, String strB) {
 32         boolean result = false;
 33         String suffix = strA.substring(strA.length() - m);
 34         result = strB.startsWith(suffix);
 35         return result;
 36     }
 37 
 38     public void createAdjMatrix() {
 39         for (int i = 0; i < vertexnum; i++) {
 40             for (int j = 0; j < vertexnum; j++) {
 41                 path[i][j] = -1;
 42                 if (hasEdge(text[i], text[j])) {
 43                     adjMatrix[i][j] = 1;
 44                     this.d[i][j] = 1;
 45                 } else {
 46                     adjMatrix[i][j] = Integer.MIN_VALUE;
 47                     this.d[i][j] = Integer.MIN_VALUE;
 48                 }
 49             }
 50         }
 51     }
 52 
 53     public void longestFloyd() {
 54         for (int i = 0; i < vertexnum; i++) {
 55             for (int j = 0; j < vertexnum; j++) {
 56                 for (int k = 0; k < vertexnum; k++) {
 57                     if (d[j][i] > Integer.MIN_VALUE
 58                             && d[i][k] > Integer.MIN_VALUE
 59                             && d[j][i] + d[i][k] > d[j][k]) {
 60                         d[j][k] = d[j][i] + d[i][k];
 61                         path[j][k] = i;
 62                         if (maxLenth < d[j][k]) {
 63                             maxLenth = d[j][k];
 64                             maxPosX = j;
 65                             maxPosY = k;
 66                         }
 67                     }
 68                 }
 69             }
 70         }
 71     }
 72 
 73     public void hasCircle() {
 74         for (int i = 0; i < vertexnum; i++) {
 75             if (d[i][i] > Integer.MIN_VALUE) {
 76                 System.out.println("Have a circle");
 77                 break;
 78             }
 79         }
 80     }
 81 
 82     public void printMaxLenth() {
 83         System.out.println("Max length is " + maxLenth);
 84     }
 85 
 86     public void printMaxLenthPath() {
 87         System.out.print(text[maxPosX] + "-->");
 88         printMaxLenthPath(maxPosX, maxPosY);
 89         System.out.println(text[maxPosY]);
 90     }
 91 
 92     private void printMaxLenthPath(int x, int y) {
 93         int k = path[x][y];
 94         if (k == -1)
 95             return;
 96         printMaxLenthPath(x, k);
 97         System.out.print(text[k] + "-->");
 98         printMaxLenthPath(k, y);
 99     }
100 
101     public void printMatrix() {
102         for (int i = 0; i < vertexnum; i++) {
103             for (int j = 0; j < vertexnum; j++) {
104                 if (adjMatrix[i][j] > Integer.MIN_VALUE) {
105                     System.out.print(adjMatrix[i][j] + " ");
106                 } else {
107                     System.out.print("* ");
108                 }
109 
110             }
111             System.out.println();
112         }
113         System.out.println("------------------------------------------------");
114         for (int i = 0; i < vertexnum; i++) {
115             for (int j = 0; j < vertexnum; j++) {
116                 if (d[i][j] > Integer.MIN_VALUE) {
117                     System.out.print(d[i][j] + " ");
118                 } else {
119                     System.out.print("* ");
120                 }
121             }
122             System.out.println();
123         }
124     }
125 
126     public static void main(String[] args) {
127         String[] text = new String[] { "abcd", "qwer", "bcde", "wert", "erty",
128                 "cdeh", "tyui", "rtyu", };
129         MaxCatenate maxCatenate = new MaxCatenate(3, text);
130         maxCatenate.createAdjMatrix();
131         maxCatenate.longestFloyd();
132         maxCatenate.printMaxLenth();
133         maxCatenate.printMaxLenthPath();
134     }
135 }