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}