《算法》第六章部分程序 part 4

▶ 书中第六章部分程序，包括在加上自己补充的代码，利用后缀树查找最长重复子串、查找最大重复子串并输出其上下文（Key word in context，KWIC）、求两字符串的最长公共子串

● 利用后缀树查找最长重复子串

 package package01;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.SuffixArrayX;

 public class class01

 {

     private class01() {}

     public static String lrs(String text)

     {

         int n = text.length();

         SuffixArrayX sa = new SuffixArrayX(text);

         String lrs = "";

         for (int i = 1; i < n; i++)                             // 遍历一次，记录最长公共前缀

         {

             int length = sa.lcp(i);

             if (length > lrs.length())

                 lrs = text.substring(sa.index(i), sa.index(i) + length);

         }

         return lrs;

     }

     public static void main(String[] args)

     {

         String text = StdIn.readAll().replaceAll("\\s+", " ");  // 空白字符全部换成 ' '

         StdOut.println("'" + lrs(text) + "'");

     }

 }

● 利用后缀树查找最大重复子串并输出其上下文（Key word in context，KWIC）

 package package01;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.SuffixArrayX;

 public class class01

 {

     private class01() {}

     public static void main(String[] args)

     {

         In in = new In(args[0]);                                                    // 命令参数，分别为输入文件和需要输出的上下文字符数量

         int context = Integer.parseInt(args[1]);

         String text = in.readAll().replaceAll("\\s+", " ");

         int n = text.length();

         SuffixArrayX sa = new SuffixArrayX(text);

         for (; StdIn.hasNextLine(); StdOut.println())

         {

             String query = StdIn.readLine();

             for (int i = sa.rank(query); i < n; i++)

             {

                 int from1 = sa.index(i), to1 = Math.min(n, from1 + query.length()); // 取 index[i] 的头和尾，要求它和 query 不同

                 if (!query.equals(text.substring(from1, to1)))

                     break;

                 int from2 = Math.max(0, sa.index(i) - context), to2 = Math.min(n, sa.index(i) + context + query.length());

                 StdOut.println(text.substring(from2, to2));                         // 向前向后各取 context 个字符

             }

         }

     }

 }

● 利用后缀树求两字符串的最长公共子串

 package package01;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.SuffixArrayX;

 public class class01

 {

     private class01() {}

     private static String lcp(String s, int p, String t, int q)     // 返回 s[p] 和 t[q] 开始的两个子串的最大公共子串

     {

         int n = Math.min(s.length() - p, t.length() - q);

         for (int i = 0; i < n; i++)                                 // 逐元素比较就好了，返回保持相等的最长子串

         {

             if (s.charAt(p + i) != t.charAt(q + i))

                 return s.substring(p, p + i);

         }

         return s.substring(p, p + n);

     }

     private static int compare(String s, int p, String t, int q)    // 比较两个后缀元素的字典序，用于判断哪个后缀元素要改用下一个

     {

         int n = Math.min(s.length() - p, t.length() - q);

         for (int i = 0; i < n; i++)

         {

             if (s.charAt(p + i) != t.charAt(q + i))

                 return s.charAt(p + i) - t.charAt(q + i);

         }

         if (s.length() - p < t.length() - q)

             return -1;

         else if (s.length() - p > t.length() - q)

             return +1;

         return  0;

     }

     public static String lcs(String s, String t)

     {

         SuffixArrayX suffix1 = new SuffixArrayX(s), suffix2 = new SuffixArrayX(t);

         String lcs = "";

         for (int i = 0, j = 0; i < s.length() && j < t.length();)   // 两个后缀数组比较 O(s.length() + t.length()) 次

         {                                                           // 每次检查两个后缀元素的最长相等子串

             int p = suffix1.index(i), q = suffix2.index(j);         // 一旦找到不相等的元素，字典序靠前的元素就取下一个后缀元素继续比较

             String x = lcp(s, p, t, q);

             if (x.length() > lcs.length())

                 lcs = x;

             if (compare(s, p, t, q) < 0)

                 i++;

             else

                 j++;

         }

         return lcs;

     }

     public static void main(String[] args)

     {

         In in1 = new In(args[0]), in2 = new In(args[1]);

         String s = in1.readAll().trim().replaceAll("\\s+", " ");

         String t = in2.readAll().trim().replaceAll("\\s+", " ");

         StdOut.println("'" + lcs(s, t) + "'");

     }

 }