001package algs63; // section 6.3 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac LCS.java 005 * Execution: java LCS file1.txt file2.txt 006 * Dependencies: In.java SuffixArray.java 007 * 008 * Reads in two text strings, replaces all consecutive blocks of 009 * whitespace with a single space, and then computes the longest 010 * common substring. 011 * 012 * Assumes that the character '\0' does not appear in either text. 013 * 014 * % java LCS mobydick.txt tale.txt 015 * ' seemed on the point of being ' 016 * 017 *************************************************************************/ 018 019 020public class XLCS { 021 022 public static void main(String[] args) { 023 In in1 = new In(args[0]); 024 In in2 = new In(args[1]); 025 String text1 = in1.readAll().replaceAll("\\s+", " "); 026 String text2 = in2.readAll().replaceAll("\\s+", " "); 027 //int N1 = text1.length(); 028 int N2 = text2.length(); 029 030 SuffixArray sa = new SuffixArray(text1 + "\0" + text2); 031 int N = sa.length(); 032 033 String substring = ""; 034 for (int i = 1; i < N; i++) { 035 036 // adjacent suffixes both from second text string 037 if (sa.select(i).length() <= N2 && sa.select(i-1).length() <= N2) continue; 038 039 // adjacent suffixes both from first text string 040 if (sa.select(i).length() > N2+1 && sa.select(i-1).length() > N2+1) continue; 041 042 // check if adjacent suffixes longer common substring 043 int length = sa.lcp(i); 044 if (length > substring.length()) 045 substring = sa.select(i).substring(0, length); 046 } 047 048 StdOut.println(substring.length()); 049 StdOut.println("'" + substring + "'"); 050 } 051}