001package algs63; // section 6.3
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac LRS.java
005 *  Execution:    java LRS < file.txt
006 *  Dependencies: StdIn.java SuffixArray.java
007 *  Data files:   http://algs4.cs.princeton.edu/63suffix/tinyTale.txt
008 *                http://algs4.cs.princeton.edu/63suffix/mobydick.txt
009 *
010 *  Reads a text string from stdin, replaces all consecutive blocks of
011 *  whitespace with a single space, and then computes the longest
012 *  repeated substring in that text using a suffix array.
013 *
014 *  % java LRS < tinyTale.txt
015 *  'st of times it was the '
016 *
017 *  % java LRS < mobydick.txt
018 *  ',- Such a funny, sporty, gamy, jesty, joky, hoky-poky lad, is the Ocean, oh! Th'
019 *
020 *  % java LRS
021 *  aaaaaaaaa
022 *  'aaaaaaaa'
023 *
024 *  % java LRS
025 *  abcdefg
026 *  ''
027 *
028 *************************************************************************/
029
030
031public class LRS {
032
033        public static void main(String[] args) {
034                String text = StdIn.readAll().replaceAll("\\s+", " ");
035                SuffixArray sa = new SuffixArray(text);
036
037                int N = sa.length();
038
039                String lrs = "";
040                for (int i = 1; i < N; i++) {
041                        int length = sa.lcp(i);
042                        if (length > lrs.length())
043                                lrs = sa.select(i).substring(0, length);
044                }
045
046                StdOut.println("'" + lrs + "'");
047        }
048}