Ois,
Fala galerinha do fórum, especial professor Coelho.
Hmm. Eu não sou chegado a tratamento especial.
Em especial por costuma ser fria 
Circular Suffix Array está determinada como n lg n
Legal que você trouxe isso para o fórum! Vamos por partes. O enunciado diz:
Performance requirements. On typical English text, your data type must use space proportional to n + R (or better) and the constructor must take time proportional to n log n (or better). The methods length() and index() must take constant time in the worst case.
Um ponto importantíssimo nessa requisitos de desempenho é o espaço utilizado pela classe CircularSuffixArray.
Não podemos utilizar o método substring() como diz o checklist:
Can I form the n circular suffixes using the substring() method from the String data type?
No. Beginning with Java 7, Update 6, the substring() method takes time and space proportional to the length of the substring().
So,explicitly forming the n circular suffixes in this way would take both quadratic time and space.
A graça dessa tarefa de programação é fazer as comparações implicitamente, sem
fazer cópias da string dada. Para isso serve o vetor index[] que da o nome
de suffix array para a estrutura. Para um arquivo com dickens.txt que tem
28965453 bytes não podemos nos dar ao luxo de usarmos 28965453 x 28965453 = 838997467495209 bytes armazenando todos os sufixos.
Estava pensando numa solução ingênua do problema que utiliza um algoritmo ...
Contudo, como comparação de strings não é constante ... a complexidade do algoritmo de comparação ..., excedendo o permitido do enunciado!
Você tem toda a razão!
O enunciado tem um On typical English text e o ckecklist diz:
What is meant by “typical English text inputs”? Inputs such as Aesop’s Fables, Moby Dick, or your most recent essay. We do not mean inputs with very long repeated substrings (such as aesop-2copies.txt or an input will 1 million consecutive As) or random inputs.
Um texto típico não contém sequências repetidas longas, que fariam com que,
como você chamou a atenção, o consumo de tempo de compareTo() fosse proibitivo.
eu deveria ignorar esse custo das operações de comparação
Não inteiramente.
No momento é ok vocês entregarem o EP usando algum algoritmo que faz na média n lg n chamadas a compareTo() para ordenar o vetor de sufixos. Um algoritmo como o 3 way quicksort (algs4, Quick3way.java, API).
Na semana que vem conversamos como podemos fazer esse algoritmo mais apropriado para strings e transformá-lo no 3-way string/radix quicksort (Quick3string.java,API)
Só por curiosidade, veja abaixo o compareTo() da classe String do Java e o strcmp() da glibc.
Olhando o código é possível ver que repetições longas fazem esse método e função trabalhar muito.
Fonte: http://developer.classpath.org/doc/java/lang/String-source.html
/**
* Compares this String and another String (case sensitive,
* lexicographically). The result is less than 0 if this string sorts
* before the other, 0 if they are equal, and greater than 0 otherwise.
* After any common starting sequence is skipped, the result is
* <code>this.charAt(k) - anotherString.charAt(k)</code> if both strings
* have characters remaining, or
* <code>this.length() - anotherString.length()</code> if one string is
* a subsequence of the other.
*
* param anotherString the String to compare against
* return the comparison
* throws NullPointerException if anotherString is null
*/
public int compareTo(String anotherString)
{
int i = Math.min(count, anotherString.count);
int x = offset;
int y = anotherString.offset;
while (--i >= 0)
{
int result = value[x++] - anotherString.value[y++];
if (result != 0)
return result;
}
return count - anotherString.count;
}
/*
Compare S1 and S2, returning less than, equal to or
greater than zero if S1 is lexicographically less than,
equal to or greater than S2.
*/
int
strcmp(char s1[], char s2[])
{
int i = 0;
while (s1[i] != '\0' && s1[i] == s2[i])
{
i = i + 1;
}
return s1[i] - s2[i];
}
/* Compare S1 and S2, returning less than, equal to or
greater than zero if S1 is lexicographically less than,
equal to or greater than S2. */
int
strcmp (const char *p1, const char *p2)
{
const unsigned char *s1 = (const unsigned char *) p1;
const unsigned char *s2 = (const unsigned char *) p2;
unsigned char c1, c2;
do
{
c1 = (unsigned char) *s1++;
c2 = (unsigned char) *s2++;
if (c1 == '\0')
return c1 - c2;
}
while (c1 == c2);
return c1 - c2;
}