Change Dir

   1: /**

   2:      * 動態規劃求最長公共子串

   3:      * 

   4:      * @param s

   5:      * @param t

   6:      * @return

   7:      */

   8:     public String getLCSByDP(String s, String t) {

   9:         int len_s = s.length();

  10:         int len_t = t.length();

  11:         String[][] num = new String[len_s][len_t];

  12:         char ch1 = '\0';

  13:         char ch2 = '\0';

  14:         int len = 0;

  15:         String res = "";

  16:         for (int i = 0; i < len_s; i++) {

  17:             for (int j = 0; j < len_t; j++) {

  18:                 ch1 = s.charAt(i);

  19:                 ch2 = t.charAt(j);

  20:                 if (ch1 != ch2) {

  21:                     num[i][j] = "";

  22:  

  23:                 } else {

  24:                     if (i == 0 || j == 0) {

  25:                         num[i][j] = ch1 + "";

  26:                     } else {

  27:                         num[i][j] = num[i - 1][j - 1] + ch1;

  28:                     }

  29:                     if (num[i][j].length() > len) {

  30:                         len = num[i][j].length();

  31:                         res = num[i][j];

  32:                     }

  33:                 }

  34:             }

  35:         }

  36:         return res;

  37:     }

   1: public static final String tail1 = "$1";

   2:     public static final String tail2 = "$2";

   3:  

   4: /**

   5:      * 求最長公共前綴LCP

   6:      * 

   7:      * @param word1

   8:      * @param word2

   9:      * @return

  10:      */

  11:     public String getLCP(String word1, String word2) {

  12:         String res = "";

  13:         int len1 = word1.length();

  14:         int len2 = word2.length();

  15:         for (int i = 0; i < Math.min(len1, len2); i++) {

  16:             if (word1.charAt(i) == word2.charAt(i)) {

  17:                 res += word1.charAt(i);

  18:             } else

  19:                 break;

  20:         }

  21:         return res;

  22:     }

  23:  

  24:     /**

  25:      * 后綴數組方法求最長公共子串

  26:      * 

  27:      * @param word1

  28:      * @param word2

  29:      * @return

  30:      */

  31:     public String getLCSByGST(String word1, String word2) {

  32:         String res = "";

  33:         

  34:         int len1 = word1.length();

  35:         int len2 = word2.length();

  36:         String gst[] = new String[len1 + len2];

  37:         for (int i = 0; i < len1; i++) {

  38:             gst[i] = mergeSuffix(word1.substring(i), word2);

  39:         }

  40:         for (int i = 0; i < len2; i++) {

  41:             gst[i + len1] = word2.substring(i) + tail2;

  42:         }

  43:         Arrays.sort(gst);

  44:         for (int i = 0; i < gst.length - 1; i++) {

  45:             String str = getLCP(gst[i], gst[i + 1]);

  46:             if (str.length() > res.length()) {

  47:                 res = str;

  48:             }

  49:         }

  50:         if (res.endsWith("$"))

  51:             res = res.substring(0, res.length() - 1);

  52:         return res;

  53:     }

  54:  

  55:     private String mergeSuffix(String word1, String word2) {

  56:         StringBuffer sb = new StringBuffer();

  57:         sb.append(word1);

  58:         sb.append(tail1);

  59:         sb.append(word2);

  60:         sb.append(tail2);

  61:         return sb.toString();

  62:     }