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}