You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
54 lines
1.5 KiB
Java
54 lines
1.5 KiB
Java
|
|
|
|
import edu.princeton.cs.introcs.StdIn;
|
|
import edu.princeton.cs.introcs.StdOut;
|
|
|
|
/*************************************************************************
|
|
* Compilation: javac LRS.java
|
|
* Execution: java LRS < file.txt
|
|
* Dependencies: StdIn.java SuffixArray.java
|
|
* Data files: http://algs4.cs.princeton.edu/63suffix/tinyTale.txt
|
|
* http://algs4.cs.princeton.edu/63suffix/mobydick.txt
|
|
*
|
|
* Reads a text string from stdin, replaces all consecutive blocks of
|
|
* whitespace with a single space, and then computes the longest
|
|
* repeated substring in that text using a suffix array.
|
|
*
|
|
* % java LRS < tinyTale.txt
|
|
* 'st of times it was the '
|
|
*
|
|
* % java LRS < mobydick.txt
|
|
* ',- Such a funny, sporty, gamy, jesty, joky, hoky-poky lad, is the Ocean, oh! Th'
|
|
*
|
|
* % java LRS
|
|
* aaaaaaaaa
|
|
* 'aaaaaaaa'
|
|
*
|
|
* % java LRS
|
|
* abcdefg
|
|
* ''
|
|
*
|
|
*************************************************************************/
|
|
|
|
|
|
public class LRS {
|
|
|
|
public static void main(String[] args) {
|
|
String text = StdIn.readAll().replaceAll("\\s+", " ");
|
|
SuffixArray sa = new SuffixArray(text);
|
|
|
|
int N = sa.length();
|
|
|
|
String lrs = "";
|
|
for (int i = 1; i < N; i++) {
|
|
int length = sa.lcp(i);
|
|
if (length > lrs.length()) {
|
|
// lrs = sa.select(i).substring(0, length);
|
|
lrs = text.substring(sa.index(i), sa.index(i) + length);
|
|
}
|
|
}
|
|
|
|
StdOut.println("'" + lrs + "'");
|
|
}
|
|
}
|